Find a Palindromic String in the Array.

Given an array of strings words[], write a program to return the first palindromic string in the array. If there is no such palindromic string present in the given array then return an empty string "".

Palindromic strings are those strings that read the same from left to right and from right to left. Example: radar(alert-passed)

Example: 
Input: words[] = {"abc", "cap", "radar", "racecar", "cook"}
Output: radar
Explanation: The first palindromic string is "radar"

Input: words[] = {"pet", "cable", "code"}
Output: ""
Explanation: There is no palindromic string, so returning an empty string.

There are multiple approaches to solving this problem, let's discuss each of them one by one:

Approach 1: Brute Force Approach.

In this approach, we are going to check each string in the array one by one if it is a palindrome. If palindrome is found then return it, else return an empty string.

Below is C++ Implementation:

//C++ Program to find Palindromic String
#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool isPalindrome(string s) {
    int n = s.length();
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - i - 1]) {
            return false;
        }
    }
    return true;
}

string firstPalindromicString(vector<string>& words) {
    for (string word : words) {
        if (isPalindrome(word)) {
            return word;
        }
    }
    return "";
}

int main() {
    vector<string> words = {"hello", "world", "racecar", "palindrome"};
    string result = firstPalindromicString(words);
    if (result == "") {
        cout << "No palindromic string found." << endl;
    } else {
        cout << "First palindromic string: " << result << endl;
    }
    return 0;
}

Output:

First palindromic string: racecar

• Time Complexity: O(n * m^2), where n is the number of words in the array and m is the length of the longest word. This is because we need to check each word in the array, and for each word, we need to check if it is a palindrome, which takes O(m^2) time.
• Space Complexity: O(1), since we are not using any additional space beyond the input array.

Approach 2: Using Two Pointers.

In this approach, we use two-pointers to compare characters from the beginning and end of each string. If the characters match, move the pointers inwards until they meet in the middle of the string. If the string is a palindrome, return it, otherwise move on to the next string in the array. 

Below is C++ Implementation:

//C++ Code for finding Palindromic String
#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool isPalindrome(string s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s[i] != s[j]) {
            return false;
        }
        i++;
        j--;
    }
    return true;
}

string firstPalindromicString(vector<string>& words) {
    for (string word : words) {
        if (isPalindrome(word)) {
            return word;
        }
    }
    return "";
}

int main() {
    vector<string> words = {"hello", "world", "racecar", "palindrome"};
    string result = firstPalindromicString(words);
    if (result == "") {
        cout << "No palindromic string found." << endl;
    } else {
        cout << "First palindromic string: " << result << endl;
    }
    return 0;
}

Output:

First palindromic string: racecar

• Time Complexity: O(n * m), where n is the number of words in the array and m is the length of the longest word. This is because we need to check each word in the array, and for each word, we need to compare each character from the beginning and end of the word, which takes O(m) time.
• Space Complexity: O(1), since we are not using any additional space beyond the input array.

Approach 3: Using Reverse String.

This approach is to reverse each string in the array and compare it to the original string. If they are equal, the string is a palindrome. Return the first palindrome found, or an empty string if no palindrome is found.

Below is C++ Implementation:

//C++ Code for Palindromic String
#include <iostream>
#include <string>
#include <vector>

using namespace std;
//function to reverse each string
string reverseString(string s) {
    int n = s.length();
    for (int i = 0; i < n / 2; i++) {
        char temp = s[i];
        s[i] = s[n - i - 1];
        s[n - i - 1] = temp;
    }
    return s;
}

string firstPalindromicString(vector<string>& words) {
    for (string word : words) {
        if (word == reverseString(word)) {
            return word;
        }
    }
    return "";
}

int main() {
    //array of string
    vector<string> words = {"hello", "world", "racecar", "palindrome"};
    //function call
    string result = firstPalindromicString(words);
    
    if (result == "") {
        cout << "No palindromic string found." << endl;
    } else {
        cout << "First palindromic string: " << result << endl;
    }
    return 0;
}

Output:

First palindromic string: racecar

• Time Complexity: O(n * m), where n is the number of words in the array and m is the length of the longest word. This is because we need to check each word in the array, and for each word, we need to reverse it, which takes O(m) time, and then compare it to the original word, which takes another O(m) time.
• Space Complexity: O(1), since we are not using any additional space beyond the input array.

Program to Find Number of Arithmetic Triplets.

Given a zero-based strictly increasing integer array arr[], and a positive integer diff. Write a program to return the number of unique arithmetic triplets.

Condition for Arithmetic Triplets:

• Index i < j < k.
• arr[j] - arr[i] == diff and,
• arr[k] - arr[j] == diff (alert-passed)

Example:
Input: arr[] = {1, 3, 5, 6, 8, 11, 15}, diff = 2
Output: 1
Explanation:
(0, 1, 2) is an arithmetic triplet because 3 - 1 = 2 and 5 - 3 = 2

Input: arr[] = {0, 1, 4, 6, 7, 10}, diff = 3
Output: 2
Explanation:
(1, 2, 4) is an arithmetic triplet because both 7 - 4 = 3 and 4 - 1 = 3.
(2, 4, 5) is an arithmetic triplet because both 10 - 7 = 3 and 7 - 4 = 3.

There are multiple ways to solve this problem and here we will discuss brute-force and optimized solutions so you can get a better understanding of how to approach similar problems. 

Approach 1: Brute Force Approach.

As the given array contains only positive numbers and elements are in sorted order, we can easily solve this problem by using three nested loops and defining the arithmetic triplet condition inside the inner loop.

Below is the C++ Implementation:

//C++ program to find arithmetic triplets
#include<iostream>
using namespace std;

//function definition
int arithmeticTriplet(int arr[], int size, int diff){
    //variable to get the count
    int count = 0;

    for(int i = 0; i < size; i++){
        for(int j = i + 1; j < size; j++){
            for(int k = j + 1; k < size; k++){
                if((arr[j] - arr[i]) == diff && (arr[k] - arr[j]) == diff){
                    count++;
                }
            }
        }
    }
    return count;
}

int main(){
    int arr[] = {0, 1, 4, 6, 7, 10};
    int size = sizeof(arr)/sizeof(arr[0]);

    int diff = 3;

    cout<<arithmeticTriplet(arr, size, diff);

    return 0;
}

Output:

2

• Time Complexity: O(n^3)
• Space Complexity: O(1)

The time complexity of the solution using the above approach is very high which is a good solution for big-size data. We have to think of a better and more optimized solution which we are going to discuss in our next approach.

Approach 2: Using a Hashmap.

Using a hashmap to store unique elements will help us reduce our time complexity. 

Steps to follow:

• Declare an unordered_map to keep track of unique elements of the array that we have seen so far and also initialize a count variable to count the number of arithmetic triplets. 
• Iterate over the given array, for each element arr[i] check if arr[i] - diff and arr[i] - 2*diff are present in our unordered_map, if yes then increase the value of count by 1.
• Insert the correct element arr[i] into the unordered_map so we can use this value to find out more arithmetic triplets.
• Return the count after processing all the elements of the given array.

Below is C++ Implementation:

//C++ code for finding arithmetic triplets
#include <iostream>
#include <unordered_set>
using namespace std;

//function declaration
int countTriplets(int arr[], int n, int diff) {
    unordered_set<int> seen;
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (seen.count(arr[i] - diff) && seen.count(arr[i] - 2 * diff)) {
            count++;
        }
        seen.insert(arr[i]);
    }

    return count;
}

int main() {

    int arr[] = {1, 3, 5, 6, 8, 11, 15};
    //size of array
    int n = sizeof(arr)/sizeof(arr[0]);

    int diff = 2;
    int count = countTriplets(arr, n, diff);
    cout << count << endl;

    return 0;
}

Output:

1

• Time Complexity: O(n) where n is the length of the input array and we only need to loop over the array once.
• Space Complexity: O(n) as we have used unordered_set to keep track of unique elements of the array.

Reverse a Number in C++ using Recursion.

Given a number num, write a C++ Program to reverse the given number using Recursion. 

Example:
Input: num = 1234
Output: 4321

Input: num = -345
Output: -543

To solve this problem, you must have some prior knowledge of C++ programming and Recursion.

Follow the steps given below to reverse a number using Recursion.

• In the reverse function, we first check if the number is zero. If it is, we return from the function, as there's nothing to reverse.
• If the number is not zero, we output the last digit of the number using the modulo operator (%).
• We then call the reverse function again, passing the number divided by 10, to remove the last digit.
• This process continues until the number becomes zero.

C++ code to Reverse a Positive Number.

//C++ Program to reverse positive number using Recursion
#include <iostream>
using namespace std;

//function call
void reverse(int num) {
    if (num == 0) {
        return;
    }

    cout << num % 10;
    reverse(num / 10);
}

int main() {
    int num;
    cout << "Enter a number: ";
    cin >> num;

    cout << "The reverse of the number is: ";
    reverse(num);
    cout << endl;
    return 0;
}

Output:

Enter a number: 4738
The reverse of the number is: 8374

• Time Complexity: O(log(n))
• Auxiliary Space: O(log(n))

Note: The above algorithm can reverse only positive numbers so to reverse both positive and negative numbers, we have made some changes in the above algorithm. (alert-passed)

Reverse a Negative Number in C++

Following steps to reverse both positive and negative numbers using recursion:

• If the number is not zero, we output the last digit of the number using the abs function and modulo operator (%).
• We then call the reverse function again, passing the absolute value of the number divided by 10, to remove the last digit.
• This process continues until the number becomes zero.
• We read the input number and check if it's negative. If it is, we output a negative sign before calling the reverse function. 

C++ code to reverse both positive and negative numbers.

//C++ Program to reverse both positive and negative num
#include <iostream>
using namespace std;

//function call
void reverse(int num) {
    if (num == 0) {
        return;
    }

    cout << abs(num % 10);
    reverse(num / 10);
}

int main() {
    int num;
    cout << "Enter a number: ";
    cin >> num;

    cout << "The reverse of the number is: ";
    //checking if num is negative
    if (num < 0) {
        cout << "-";
    }
    
    reverse(abs(num));
    cout << endl;
    return 0;
}

Output:

Enter a number: -14738
The reverse of the number is: -83741

• Time Complexity: O(log(n))
• Auxiliary Space: O(log(n))

C++ Program to Find Sum of Digits of a Number.

Given a number num, write a C++ Program to find the sum of digits of the number. 

Example:

Input: num = 1432
Output: 10

Explanation: 1 + 4 + 3 + 2 = 10

Input: num = 9831
Output: 21

Explanation: 9 + 8 + 3 + 1 = 21

There are multiple ways to solve this problem, let's understand each of them one by one:

Approach 1: Using the modulo operator and while loop.

Follow the below steps to sum the digits of a number:

• Use a while loop to continuously extract the last digit of the number using the modulo operator (%).
• Add the extracted digit to a running total (sum), and then remove it from the number using the division (/) operator.
• This process continues until the number becomes zero.

C++ Program sums the digits of a number. 

//C++ Program to sum the digits of a number
#include <iostream>
using namespace std;

int main() {
    int num, sum = 0;
    cout << "Enter a number: ";
    cin >> num;

    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }

    cout << "Sum of digits: " << sum << endl;
    return 0;
}

Output:

Enter a number: 1345
Sum of digits: 13

• Time Complexity: O(n)
• Space Complexity: O(1)

Approach 2: Using String Streams.

Follow the below steps:

• Use a string stream to convert the integer number into a string. 
• Use a for loop to iterate over each character in the string and add its integer value (obtained by subtracting the ASCII value of the character '0') to a running total (sum).
• Print the value of the sum as an output.

C++ code implementation of the above approach.

//C++ code implementation for finding sum of diigts of a num
#include <iostream>
#include <sstream>

using namespace std;

int main() {
    int num, sum = 0;
    cout << "Enter a number: ";
    cin >> num;

    stringstream ss;
    ss << num;

    string str = ss.str();
    for (char c : str) {
        sum += c - '0';
    }

    cout << "Sum of digits: " << sum << endl;
    return 0;
}

Output:

Enter a number: 1349
Sum of digits: 17

• Time Complexity: O(n)
• Space Complexity: O(n)

C++ Program to Check Whether Number is Even or Odd.

Given a number num, write a C++ Program to check whether the given number is Even or Odd. 

Example:

Input: num = 8
Output: Even

Input: num = 11
Output: Odd

Note: To understand this example, you must know the basics of C++ programming and if..else statements. 

Approach 1: If the given number is divisible by 2 then the number is Even and if the number is not divisible by 2 then the number is Odd.

Pseudo Code:

Step 1: Read a number "num"

Step 2: If "num % 2" is equal to 0, then
    Step 2.1: Print "num is an even number"

Step 3: Else,
    Step 3.1: Print "num is an odd number"

Step 4: End

Following C++ Program to check if a number is Even or Odd:

//C++ Program to check Even or Odd
#include <iostream>
using namespace std;

int main() {
    int num;
    cout << "Enter a number: ";
    cin >> num;

    if (num % 2 == 0) {
        cout << num << " is an even number" << endl;
    } else {
        cout << num << " is an odd number" << endl;
    }

    return 0;
}

Output:

Enter a number: 12
12 is an even number

Explanation: 

The program takes an input number and calculates the remainder when it is divided by 2. If the remainder is 0, then the number is even, and if it's not 0, then the number is odd.

Approach 2: 

In this approach, we use the bitwise "&" operator to check if the least significant bit (LSB) of the number is set. If the LSB is set, then the number is odd, and if it's not set, then the number is even. 

Below is the C++ code Implementation:

//C++ Program to check Odd and Even using Bitwise
#include <iostream>
using namespace std;

int main() {
    int num;
    cout << "Enter a number: ";
    cin >> num;

    if (num & 1) {
        cout << num << " is an odd number" << endl;
    } else {
        cout << num << " is an even number" << endl;
    }

    return 0;
}

Output:

Enter a number: 11
11 is an odd number

Note: This approach is faster than the modulo operator (%), as the bitwise operator is typically faster than the modulo operator. (alert-success)

Python Program to Add Item in a Tuple.

Tuples are immutable, meaning their values cannot be changed once they are created. This can be a disadvantage when you need to add an element to an existing tuple. To overcome this, there are several different approaches you can take to add an item to a tuple in Python:

List of Approaches to Add Item in a Tuple.

1. Concatenation: One way to add an item to a tuple is to concatenate two tuples together using the + operator.

Example Code:

# Adding Item to Tuple Using Concatenation
original_tuple = (1, 2, 3)
new_item = 4
updated_tuple = original_tuple + (new_item,)

print(updated_tuple)

Output:

(1, 2, 3, 4)

Advantages and Disadvantages of Concatenation on Tuple.

Advantages:

• Simple and easy to understand.
• Suitable for adding a single item to a tuple.

Disadvantages:

• Not efficient for adding multiple items to a tuple.
• Creates a new tuple, which requires additional memory.

2. Conversion to a list: Another approach is to convert the tuple to a list, add the item to the list, and then convert the list back to a tuple.

Example Code:

# Adding Item to Tuple Using Conversion to a list
original_tuple = (1, 2, 3)
new_item = 4
updated_list = list(original_tuple)
updated_list.append(new_item)
updated_tuple = tuple(updated_list)

print(updated_tuple)

Output:

(1, 2, 3, 4)

Advantages and Disadvantages of Conversion of Tuple to List.

Advantages:

• Suitable for adding multiple items to a tuple.
• The append method can be used to add various items to the list.

Disadvantages:

• Converting the list back to a tuple requires additional time and memory.
• Not as efficient as other approaches for adding a single item to a tuple.

3. Using slicing: You can also create a new tuple by slicing the original tuple and adding the new item in between.

Example Code:

# Adding Item to Tuple Using Slicing 
original_tuple = (1, 2, 3)
new_item = 4
updated_tuple = original_tuple[:len(original_tuple)] + 

(new_item,) + original_tuple[len(original_tuple):]

print(updated_tuple)

Output:

(1, 2, 3, 4)

Advantages and Disadvantages of Slicing on Tuple.

Advantages:

• Suitable for adding a single item to a tuple.
• Does not require conversion to a list.

Disadvantages:

• Complex and less readable than other approaches.
• Creates a new tuple, which requires additional memory.

You can use all these approaches based on your requirement, which can be decided by the number of items that need to be added to the tuple and the size. 

Read more:

How to add Elements in a List in Python?

How To Add Elements to List in Python?

In this tutorial, we are going to understand different approaches to add elements to a list in Python. 

There are three different ways of adding elements to a List in Python. 

• Using the append() method.
• Using the extend() method.
• Using the Concatenation operator (+).

Using the append() method.

In this approach, we use the append() method to add elements to the end of the list. The append() method takes one argument, which is the element to be added to the list.

Python code:

my_list = []
my_list.append(1)
my_list.append(2)
my_list.append(3)
print(my_list)  # Output: [1, 2, 3]

Using the extend() method.

In this approach, we use the extend() method to add multiple elements to the end of the list. The extend() method takes one argument, which is a list of elements to be added to the original list.

Python code:

my_list = [1, 2]
my_list.extend([3, 4, 5])
print(my_list)  # Output: [1, 2, 3, 4, 5]

Using the Concatenation operator (+).

In this approach, we use the concatenation operator + to add multiple elements to the end of the list. The concatenation operator takes two lists as operands and returns a new list which is the concatenation of the two lists.

Python code:

my_list = [1, 2]
my_list = my_list + [3, 4, 5]
print(my_list)  # Output: [1, 2, 3, 4, 5]

Python Program to Add Digits of a Number.

Given a number num, write a Python program to add digits of the given number and print the sum as an output.

Example:

Input: num = 145
Output: 10

Explanation: 1 + 4 + 5 = 10

Input: num = 9231
Output: 15

Explanation: 9 + 2 + 3 + 1 = 15

There are multiple approaches by which we can solve this problem, let's discuss each of them one by one.

Approach 1: Using integer division and modulo operator.

In this approach, we use the modulo operator % to extract the last digit of the number and add it to the sum variable. We then use integer division // to remove the last digit from the number and repeat the process until the number becomes zero.

Python code:

# Python program to add digits of a number
def add_digits(n):
    sum = 0
    while n > 0:
        sum += n % 10
        n = n // 10
    return sum

# take input from the user
num = int(input("Enter a number: "))  

print(add_digits(num))    

Output:

Enter a number: 123
6

• Time Complexity: O(number of digits)
• Space Complexity: O(1)

Approach 2: Using string conversion and for loop.

In this approach, we first convert the number to a string and then use a for loop to iterate over each character in the string. We convert each character back to an integer and add it to the sum variable.

Python code:

# Python program to add digits of a number
def add_digits(n):
    n = str(n)
    sum = 0
    for digit in n:
        sum += int(digit)
    return sum

# take input from the user
num = int(input("Enter a number: "))  

print(add_digits(num))    

Output:

Enter a number: 4753
19

• Time Complexity: O(number of digits)
• Space Complexity: O(1)

Approach 3: Using Recursion.

In this approach, we use recursion, to sum up, the digits of the number. The base case is when the number becomes zero, in which case we return zero. Otherwise, we extract the last digit using the modulo operator and add it to the result of the recursive call to add_digits with the number divided by 10.

Python Code:

# Python program to add digits of a number
def add_digits(n):
    if n == 0:
        return 0
    return n % 10 + add_digits(n // 10)

# take input from the user
num = int(input("Enter a number: "))  

print(add_digits(num))    

Output:

Enter a number: 542
11

• Time Complexity: O(number of digits)
• Space Complexity: O(n) 

Read more:

Python Program to Reverse a Number.

Python Program to Check Armstrong Number.

Python Program to Check Prime Number.