C Program to Check if a Given String is Palindrome

// A function to check if a string str is palindrome
void isPalindrome(char str[])
{
    // Start from leftmost and rightmost corners of str
    int l = 0;
    int h = strlen(str) - 1;
  
    // Keep comparing characters while they are same
    while (h > l)
    {
        if (str[l++] != str[h--])
        {
            printf("%s is Not Palindrome", str);
            return;
        }
    }
    printf("%s is palindrome", str);
}
  
// Driver program to test above function
int main()
{
    isPalindrome("abba");
    isPalindrome("abbccbba");
    isPalindrome("geeks");
    return 0;
}

Recursive function to check if a string is palindrome

// A recursive C++ program to 
// check whether a given number
// is palindrome or not
#include <bits/stdc++.h>
using namespace std;
  
// A recursive function that
// check a str[s..e] is
// palindrome or not.
bool isPalRec(char str[], 
              int s, int e)
{
      
    // If there is only one character
    if (s == e)
    return true;
  
    // If first and last
    // characters do not match
    if (str[s] != str[e])
    return false;
  
    // If there are more than 
    // two characters, check if 
    // middle substring is also 
    // palindrome or not.
    if (s < e + 1)
    return isPalRec(str, s + 1, e - 1);
  
    return true;
}
  
bool isPalindrome(char str[])
{
    int n = strlen(str);
      
    // An empty string is 
    // considered as palindrome
    if (n == 0)
        return true;
      
    return isPalRec(str, 0, n - 1);
}
  
// Driver Code
int main()
{
    char str[] = "geeg";
  
    if (isPalindrome(str))
    cout << "Yes";
    else
    cout << "No";
  
    return 0;
}

Longest Palindromic Substring

Given a string, find the longest substring which is palindrome. 

For example, 

Input: Given string :"forgeeksskeegfor", 
Output: "geeksskeeg"

Input: Given string :"Geeks", 
Output: "ee"

Method 2: Dynamic Programming. 
Approach: The time complexity can be reduced by storing results of sub-problems. The idea is similar to this post.  

  1. Maintain a boolean table[n][n] that is filled in bottom up manner.
  2. The value of table[i][j] is true, if the substring is palindrome, otherwise false.
  3. To calculate table[i][j], check the value of table[i+1][j-1], if the value is true and str[i] is same as str[j], then we make table[i][j] true.
  4. Otherwise, the value of table[i][j] is made false.
  5. We have to fill table previously for substring of length = 1 and length =2 because 
    as we are finding , if table[i+1][j-1] is true or false , so in case of 
    (i) length == 1 , lets say i=2 , j=2 and i+1,j-1 doesn’t lies between [i , j] 
    (ii) length == 2 ,lets say i=2 , j=3 and i+1,j-1 again doesn’t lies between [i , j].

Below is the implementation of the above approach: 

// A C++ dynamic programming
// solution for longest palindrome
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print a substring
// str[low..high]
void printSubStr(
    string str, int low, int high)
{
    for (int i = low; i <= high; ++i)
        cout << str[i];
}
 
// This function prints the
// longest palindrome substring
// It also returns the length of
// the longest palindrome
int longestPalSubstr(string str)
{
    // get length of input string
    int n = str.size();
 
    // table[i][j] will be false if substring
    // str[i..j] is not palindrome.
    // Else table[i][j] will be true
    bool table[n][n];
 
    memset(table, 0, sizeof(table));
 
    // All substrings of length 1
    // are palindromes
    int maxLength = 1;
 
    for (int i = 0; i < n; ++i)
        table[i][i] = true;
 
    // check for sub-string of length 2.
    int start = 0;
    for (int i = 0; i < n - 1; ++i) {
        if (str[i] == str[i + 1]) {
            table[i][i + 1] = true;
            start = i;
            maxLength = 2;
        }
    }
 
    // Check for lengths greater than 2.
    // k is length of substring
    for (int k = 3; k <= n; ++k) {
        // Fix the starting index
        for (int i = 0; i < n - k + 1; ++i) {
            // Get the ending index of substring from
            // starting index i and length k
            int j = i + k - 1;
 
            // checking for sub-string from ith index to
            // jth index iff str[i+1] to str[j-1] is a
            // palindrome
            if (table[i + 1][j - 1] && str[i] == str[j]) {
                table[i][j] = true;
 
                if (k > maxLength) {
                    start = i;
                    maxLength = k;
                }
            }
        }
    }
 
    cout << "Longest palindrome substring is: ";
    printSubStr(str, start, start + maxLength - 1);
 
    // return length of LPS
    return maxLength;
}
 
// Driver Code
int main()
{
    string str = "forgeeksskeegfor";
    cout << "\nLength is: "
         << longestPalSubstr(str);
    return 0;
}

Output: 

Longest palindrome substring is: geeksskeeg
Length is: 10

Complexity Analysis:  

  • Time complexity: O(n^2). 
    Two nested traversals are needed.
  • Auxiliary Space: O(n^2). 
    Matrix of size n*n is needed to store the dp array.
XOR Linked List – A Memory Efficient Doubly Linked List | Set 1
  • Difficulty Level : Medium
  •  Last Updated : 28 Sep, 2018

An ordinary Doubly Linked List requires space for two address fields to store the addresses of previous and next nodes. A memory efficient version of Doubly Linked List can be created using only one space for address field with every node. This memory efficient Doubly Linked List is called XOR Linked List or Memory Efficient as the list uses bitwise XOR operation to save space for one address. In the XOR linked list, instead of storing actual memory addresses, every node stores the XOR of addresses of previous and next nodes.

Consider the above Doubly Linked List. Following are the Ordinary and XOR (or Memory Effiecient) representations of the Doubly Linked List.

Ordinary Representation:
Node A:
prev = NULL, next = add(B) // previous is NULL and next is address of B

Node B:
prev = add(A), next = add(C) // previous is address of A and next is address of C



Node C:
prev = add(B), next = add(D) // previous is address of B and next is address of D

Node D:
prev = add(C), next = NULL // previous is address of C and next is NULL

XOR List Representation:
Let us call the address variable in XOR representation npx (XOR of next and previous)

Node A:
npx = 0 XOR add(B) // bitwise XOR of zero and address of B

Node B:
npx = add(A) XOR add(C) // bitwise XOR of address of A and address of C

Node C:
npx = add(B) XOR add(D) // bitwise XOR of address of B and address of D

Node D:
npx = add(C) XOR 0 // bitwise XOR of address of C and 0

Traversal of XOR Linked List:
We can traverse the XOR list in both forward and reverse direction. While traversing the list we need to remember the address of the previously accessed node in order to calculate the next node’s address. For example when we are at node C, we must have address of B. XOR of add(B) and npx of C gives us the add(D). The reason is simple: npx(C) is “add(B) XOR add(D)”. If we do xor of npx(C) with add(B), we get the result as “add(B) XOR add(D) XOR add(B)” which is “add(D) XOR 0” which is “add(D)”. So we have the address of next node. Similarly we can traverse the list in backward direction.

XOR Linked List – A Memory Efficient Doubly Linked List | Set 2
  • Difficulty Level : Medium
  •  Last Updated : 01 Feb, 2021

In the previous post, we discussed how a Doubly Linked can be created using only one space for the address field with every node. In this post, we will discuss the implementation of memory-efficient doubly linked list. We will mainly discuss the following two simple functions.

  1. A function to insert a new node at the beginning.
  2. A function to traverse the list in forward direction.

In the following code, insert() function inserts a new node at the beginning. We need to change the head pointer of Linked List, that is why a double pointer is used (See this). Let us first discuss few things again that have been discussed in the previous post. We store XOR of next and previous nodes with every node and we call it npx, which is the only address member we have with every node. When we insert a new node at the beginning, npx of new node will always be XOR of NULL and current head. And npx of the current head must be changed to XOR of new node and node next to the current head.
printList() traverses the list in forward direction. It prints data values from every node. To traverse the list, we need to get pointer to the next node at every point. We can get the address of next node by keeping track of current node and previous node. If we do XOR of curr->npx and prev, we get the address of next node. 

/* C++ Implementation of Memory
efficient Doubly Linked List */
#include <bits/stdc++.h>
#include <cinttypes>
using namespace std;
 
// Node structure of a memory
// efficient doubly linked list
class Node
{
    public:
    int data;
    Node* npx; /* XOR of next and previous node */
};
 
/* returns XORed value of the node addresses */
Node* XOR (Node *a, Node *b)
{
    return reinterpret_cast<Node *>(
      reinterpret_cast<uintptr_t>(a) ^
      reinterpret_cast<uintptr_t>(b));
}
 
/* Insert a node at the beginning of the
XORed linked list and makes the newly
inserted node as head */
void insert(Node **head_ref, int data)
{
    // Allocate memory for new node
    Node *new_node = new Node();
    new_node->data = data;
 
    /* Since new node is being inserted at the
    beginning, npx of new node will always be
    XOR of current head and NULL */
    new_node->npx = *head_ref;
 
    /* If linked list is not empty, then npx of
    current head node will be XOR of new node
    and node next to current head */
    if (*head_ref != NULL)
    {
        // *(head_ref)->npx is XOR of NULL and next.
        // So if we do XOR of it with NULL, we get next
        (*head_ref)->npx = XOR(new_node, (*head_ref)->npx);
    }
 
    // Change head
    *head_ref = new_node;
}
 
// prints contents of doubly linked
// list in forward direction
void printList (Node *head)
{
    Node *curr = head;
    Node *prev = NULL;
    Node *next;
 
    cout << "Following are the nodes of Linked List: \n";
 
    while (curr != NULL)
    {
        // print current node
        cout<<curr->data<<" ";
 
        // get address of next node: curr->npx is
        // next^prev, so curr->npx^prev will be
        // next^prev^prev which is next
        next = XOR (prev, curr->npx);
 
        // update prev and curr for next iteration
        prev = curr;
        curr = next;
    }
}
 
// Driver code
int main ()
{
    /* Create following Doubly Linked List
    head-->40<-->30<-->20<-->10 */
    Node *head = NULL;
    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);
    insert(&head, 40);
 
    // print the created list
    printList (head);
 
    return (0);
}
 
// This code is contributed by rathbhupendra

Output
Following are the nodes of Linked List: 
40 30 20 10
Program to check if an array is sorted or not (Iterative and Recursive)
  • Difficulty Level : Easy
  •  Last Updated : 22 Dec, 2020

Given an array of size n, write a program to check if it is sorted in ascending order or not. Equal values are allowed in an array and two consecutive equal values are considered sorted.

Examples: 

Input : 20 21 45 89 89 90
Output : Yes

Input : 20 20 45 89 89 90
Output : Yes

Input : 20 20 78 98 99 97
Output : No

Recursive approach:
The basic idea for the recursive approach:  

1: If size of array is zero or one, return true.
2: Check last two elements of array, if they are
   sorted, perform a recursive call with n-1
   else, return false.
If all the elements will be found sorted, n will
eventually fall to one, satisfying Step 1.

Below is the implementation using recursion:

// Recursive approach to check if an
// Array is sorted or not
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns 0 if a pair
// is found unsorted
int arraySortedOrNot(int arr[], int n)
{
    // Array has one or no element or the
    // rest are already checked and approved.
    if (n == 1 || n == 0)
        return 1;
 
    // Unsorted pair found (Equal values allowed)
    if (arr[n - 1] < arr[n - 2])
        return 0;
 
    // Last pair was sorted
    // Keep on checking
    return arraySortedOrNot(arr, n - 1);
}
 
// Driver code
int main()
{
    int arr[] = { 20, 23, 23, 45, 78, 88 };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (arraySortedOrNot(arr, n))
        cout << "Yes\n";
    else
        cout << "No\n";
}

Output:

Yes

Time Complexity: O(n) 
Auxiliary Space: O(n) for Recursion Call Stack.

Another Recursive approach:

// C++ Recursive approach to check if an
// Array is sorted or not
#include <iostream>
using namespace std;
 
// Function that returns true if array is
// sorted in non-decreasing order.
bool arraySortedOrNot(int a[], int n)
{
     
    // Base case
    if (n == 1 || n == 0)
    {
        return true;
    }
     
    // Check if present index and index
    // previous to it are in correct order
    // and rest of the array is also sorted
    // if true then return true else return
    // false
    return a[n - 1] >= a[n - 2] &&
     arraySortedOrNot(a, n - 1);
}
 
// Driver code
int main()
{
    int arr[] = { 20, 23, 23, 45, 78, 88 };
    int n = sizeof(arr) / sizeof(arr[0]);
     
    // Function Call
    if (arraySortedOrNot(arr, n))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
     
    return 0;
}
 
// This code is contributed by avanitrachhadiya2155
Output
Yes

Time Complexity: O(n) 
Auxiliary Space: O(n) for Recursion Call Stack.

Iterative approach: The idea is pretty much the same. The benefit of the iterative approach is it avoids the usage of recursion stack space and recursion overhead.

Below is the implementation using iteration: 

// C++ program to check if an
// Array is sorted or not
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if array is
// sorted in non-decreasing order.
bool arraySortedOrNot(int arr[], int n)
{
    // Array has one or no element
    if (n == 0 || n == 1)
        return true;
 
    for (int i = 1; i < n; i++)
 
        // Unsorted pair found
        if (arr[i - 1] > arr[i])
            return false;
 
    // No unsorted pair found
    return true;
}
 
// Driver code
int main()
{
    int arr[] = { 20, 23, 23, 45, 78, 88 };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (arraySortedOrNot(arr, n))
        cout << "Yes\n";
    else
        cout << "No\n";
}

Output: 

Yes

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

Check if the Left View of the given tree is sorted or not
  • Last Updated : 08 Jul, 2020

Given a tree, our task is to check whether its left view is sorted or not. If it is then return true else false.

Examples:

Input:

Output: true
Explanation:
The left view for the tree would be 10, 20, 50 which is in sorted order.

Approach:

To solve the problem mentioned above we have to perform level order traversal on the tree and look for the very first node of each level. Then initialize a variable to check whether its left view is sorted or not. If it is not sorted, then we can break the loop and print false else loop goes on and at last print true.

// C++ implementation to Check if the Left
// View of the given tree is Sorted or not
  
#include <bits/stdc++.h>
using namespace std;
  
// Binary Tree Node
struct node {
    int val;
    struct node *right, *left;
};
  
// Utility function to create a new node
struct node* newnode(int key)
{
    struct node* temp = new node;
    temp->val = key;
    temp->right = NULL;
    temp->left = NULL;
  
    return temp;
}
  
// Fucntion to find left view
// and check if it is sorted
void func(node* root)
{
    // queue to hold values
    queue<node*> q;
  
    // variable to check whether
    // level order is sorted or not
    bool t = true;
    q.push(root);
  
    int i = -1, j = -1, k = -1;
  
    // Iterate until the queue is empty
    while (!q.empty()) {
        int h = q.size();
  
        // Traverse every level in tree
        while (h > 0) {
            root = q.front();
  
            // variable for initial level
            if (i == -1) {
                j = root->val;
            }
            // checking values are sorted or not
            if (i == -2) {
                if (j <= root->val) {
                    j = root->val;
                    i = -3;
                }
                else {
                    t = false;
                    break;
                }
            }
            // Push left value if it is not null
            if (root->left != NULL) {
                q.push(root->left);
            }
            // Push right value if it is not null
            if (root->right != NULL) {
                q.push(root->right);
            }
            h = h - 1;
  
            // Pop out the values from queue
            q.pop();
        }
        i = -2;
  
        // Check if the value are not
        // sorted then break the loop
        if (t == false) {
            break;
        }
    }
    if (t)
        cout << "true" << endl;
  
    else
        cout << "false" << endl;
}
  
// Driver code
int main()
{
    struct node* root = newnode(10);
    root->right = newnode(50);
    root->right->right = newnode(15);
    root->left = newnode(20);
    root->left->left = newnode(50);
    root->left->right = newnode(23);
    root->right->left = newnode(10);
  
    func(root);
  
    return 0;
}
Output:
true

Time complexity: O(N)














Comments

Post a Comment

Popular posts from this blog

[13 Feb 2020] Check if a given sequence of moves for a robot is circular or not

Check if a given sequence of moves for a robot is circular or not Link:  https://www.youtube.com/watch?v=f7Zd8hEbCz0 Given a sequence of moves for a robot, check if the sequence is circular or not. A sequence of moves is circular if first and last positions of robot are same. A move can be on of the following. G - Go one unit L - Turn left R - Turn right Input: path[] = "GLGLGLG" Output: Given sequence of moves is circular Input: path[] = "GLLG" Output: Given sequence of moves is circular The idea is to consider the starting position as (0, 0) and direction as East (We can pick any values for these). If after the given sequence of moves, we come back to (0, 0), then given sequence is circular, otherwise not. N | | W -------------- E | | S The move ‘G’ changes either x or y according to following rules. a) If current direction is North, then ‘G’ increments y and doesn’t cha...
Read more

Typical Programs in C/C++

  Sum of two large numbers Difficulty Level :   Medium   Last Updated :  04 Jun, 2019 Given two numbers as strings. The numbers may be very large (may not fit in long long int), the task is to find sum of these two numbers. Examples: Input : str1 = "3333311111111111", str2 = "44422222221111" Output : 3377733333332222 Input : str1 = "7777555511111111", str2 = "3332222221111" Output : 7780887733332222 The idea is based on school mathematics. We traverse both strings from end, one by one add digits and keep track of carry. To simplify the process, we do following: 1) Reverse both strings. 2) Keep adding digits one by one from 0’th index (in reversed strings) to end of smaller string, append the sum % 10 to end of result and keep track of carry as sum/10. 3) Finally reverse the result. // C++ program to find sum of two large numbers. #include<bits/stdc++.h> using namespace std;     // Function for finding sum of la...
Read more