Monthly Archives: April 2016

Binary Search Trees from keys 1 to n

Construct Binary Search Trees from keys 1 to n

Problem statement to construct a Binary Search Tree(BST) from keys 1 to n.

We are given a list of consecutive numbers from 1 to . Determine the number of binary trees that can be constructed from these numbers.

Example for building a Binary Search Tree from keys 1 to n:

Input: 1,2,3
Output:
    3   3         1          1      2
   /     \         \        /      / \
  2       2         3      2      1   3
 /         \       /        \
1           1     2          3

Solution to construct the binary search trees from consecutive keys:

Nodes in the left subtree are smaller and right subtree nodes are greater than the root node. Using this rule, we can construct binary search trees.For a root i, left subtree will have nodes 1 to i-1 and can form x different trees while right subtree will have i+1 to n nodes and can form y different trees. So total possible trees = x*y. Also, we can iterate i from 1 to n. Therefore, total number actually comes out to be equal to a CATALAN NUMBER.

Algorithm to build the binary search trees from consecutive keys:

  1. Initialize a vector list.
  2. For an integer i which ranges from 1 to n,
    1. Create the root node with root->data = i.
    2.Recursively build the left subtree.
    3. Recursively build the right subtree.
  3. Iterate for all left subtrees.
    1.Iterate for all right subtrees.

Code in C++ to build a Binary Search Tree (BST) from the keys:

#include <bits/stdc++.h>
using namespace std;

struct node
{
   int data;
   node* left;
   node* right;
};

/*Function to create a new node*/
node* newNode(int key)
{
   node* temp = new node;
   temp->data = key;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
   
}

/*Function for preorder traversal of tree*/
void preorder(node *root)
{
   if(!root)
      return;
   cout<<root->data<<" ";
   preorder(root->left);
   preorder(root->right);
}

/*Function to construct a tree*/
vector<node*> buildTree(int start, int end)
{
   vector <node*> list;
   
   if(start>end)
   {
      list.push_back(NULL);
      return list;
   }
   
   for(int i=start; i<=end; i++)
   {
      /*build left subtree*/
      vector <node*> leftSubtree = buildTree(start,i-1);
      
      /*build right subtree*/
      vector <node*> rightSubtree = buildTree(i+1,end);
      
      /*connecting left and right subtrees*/
      
      for(int j=0; j<leftSubtree.size();j++)
      {
         node* left = leftSubtree[j];
         
         for(int k=0; k<rightSubtree.size();k++)
         {
            node* right = rightSubtree[k];
            node* root = newNode(i);
            root->left = left;
            root->right = right;
            list.push_back(root);
         }
      }
   }
   return list;
}

int main() {
   vector <node*> totalTrees = buildTree(1,3);
   
   /*print preorder traversal of all trees*/
   cout<<"Preorder traversal of trees:\n";
   for(int i=0; i<totalTrees.size(); i++)
   {
      preorder(totalTrees[i]);
      cout<<endl;
   }
   return 0;
}

OUTPUT:

Preorder traversal of trees:
1 2 3 
1 3 2 
2 1 3 
3 1 2 
3 2 1

Time Complexity: O(n2)

Find position of an element in a sorted array of infinite numbers

Find position of an element in a sorted array of infinite numbers

In this post we deal with the problem of finding position of an element in a given array which is sorted and has infinite numbers.

Find position of an element in a sorted array of infinite numbers Problem Statement

Given a sorted array of infinite numbers, we need to  search for an element in the array. Since it’s given to us in the question that the array is sorted, the first approach which clicks into mind is binary search, but the problem here is that we don’t know the exact size of array. The number of elements in the array is infinite and so we are unable to decide an upper bound.

Find position of an element in a sorted array of infinite numbers Problem Example

Let the input arr[] = { 24, 6, 12, 78, 45, 1, 34...}
Element to be found = 1
Output = Element found at index 5

Find position of an element in a sorted array of infinite numbers Problem Solution

We cannot solve the problem using binary search algorithm as explained above. If the array is infinite, that means we don’t have proper bounds to apply binary search. So in order to find position of key(the element whose position has to be found) , first we find bounds and then apply binary search algorithm.

Algorithm:

  1. Let low be pointing to 1st element and high pointing to 2nd element of array.
  2. Now compare key with high index element.
  3. If it is greater than high index element then copy high index in low index and double the high index.
  4. If it is smaller, then apply binary search on high and low indices found.

Find position of an element in a sorted array of infinite numbers Problem Solution code in C++ :

#include<bits/stdc++.h>
using namespace std;
 
// Simple binary search algorithm
int binarySearch(int arr[], int l, int h, int x)
{
    if (h>=l)
    {
        int mid = l + (h - l)/2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid-1, x);
        return binarySearch(arr, mid+1, h, x);
    }
    return -1;
}
 
/*Function takes an infinite size array and a key and 
  returns its position if found else -1.We don't know size
  of arr[] and we assume size to be infinite in this function.
  Therefore, there is no index out of bound checking*/
int findPos(int arr[], int key)
{
    int l = 0, h = 1;
    int val = arr[0];
 
    // Find h to do binary search
    while (val < key)
    {
        l = h;        // store previous high
        h = 2*h;      // double high index
        val = arr[h]; // update new val
    }
 
    /* at this point we have updated low and high indices,
        thus use binary search between them*/
    return binarySearch(arr, l, h, key);
}
 
// Driver program
int main()
{
    int arr[] = {3, 5, 7, 9, 10, 90, 100, 130, 140, 160, 170};
    /*We do not specify size as we assume array to be infinite*/
    int ans = findPos(arr, 10);
    if (ans==-1)
        cout << "Element not found";
    else
        cout << "Element found at index " << ans;
    return 0;
}

 Output:

Element found at index 4

Time Complexity : O(p)
Space Complexity:O(1)

Explanation of complexity:Let p be the position of element to be searched. Number of steps for finding high index ‘h’ is O(Log p). The value of ‘h’ must be less than 2*p. The number of elements between h/2 and h must be O(p). Therefore, time complexity of Binary Search step is also O(Log p) and overall time complexity is 2*O(Log p) which is O(Log p).

Arrange elements of given array to form largest number

Arrange elements of given array to form largest number

In this post we learn how to form the largest number from all the given elements of the input array.

Arrange elements of given array to form largest number Problem Statement:

Given an array of numbers,we need to arrange them in a way that yields the largest value possible of all the combinations that can be made.

Arrange elements of given array to form largest number Problem Example:

Let the input numbers given are : {1, 34, 3, 98, 9, 76, 45, 4}
Arrangement which gives the largest value : 998764543431

Arrange elements of given array to form largest number Problem Solution:

The first thing that we would like to try is to sort the numbers in decreasing array and print the result but simply sorting doesn’t work. For example, 548 is greater than 60, but in output 60 comes before 548. As a second example, 98 is greater than 9, but 9 comes before 98 in output.
The idea is to use any comparison based sorting algorithm. In the used sorting algorithm, instead of using the default comparison, write a comparison function MyCompare() and use it to sort numbers.

Algorithm:

  1. Given two numbers X and Y, MyCompare() must compare these two.
  2. We compare two numbers XY (Y appended at the end of X) and YX (X appended at the end of Y).
  3. If XY is larger, then X should come before Y in output, else Y should come before.
  4. Eg -let X and Y be 542 and 60. To compare X and Y, we compare 54260 and 60542
  5. Since 60542 is greater than 54260, we put Y first.

Arrange elements of given array to form largest number Problem Solution Code in C++:

  
#include <bits/stdc++.h> 
using namespace std;   

// A comparison function which is used by sort() in printLargest()
 int myCompare(string X, string Y) 
{     
    // first append Y at the end of X
    string XY = X.append(Y);
  
    // then append X at the end of Y
    string YX = Y.append(X);
 
    // Now see which of the two formed numbers is greater
    return XY.compare(YX) > 0 ? 1: 0;
}
/* The function that prints the arrangement with largest
   value. It accepts a vector of strings */
void printLargest(vector<string> arr)
{
    /*Sort the numbers using library sort funtion.It uses our
     comparison function myCompare() to compare two strings.*/
    sort(arr.begin(), arr.end(), myCompare);
 
    for (int i=0; i < arr.size() ; i++ )
        cout << arr[i];
}
 
// driver program to test above functions
int main()
{
    vector<string> arr;
 
    //output should be 998764543431
    arr.push_back("1");
    arr.push_back("34");
    arr.push_back("3");
    arr.push_back("98");
    arr.push_back("9");
    arr.push_back("76");
    arr.push_back("45");
    arr.push_back("4");
    printLargest(arr);
    
    return 0;
}

Output:

998764543431

Time Complexity:O(M logN)
Space Complexity: O(N)

Rearrange Positive and Negative numbers in an array

Rearrange Positive and Negative numbers in an array

In this post we solve the problem of rearranging positive and negative elements of an array such that they are placed alternatively in the same array.

Rearrange Positive and Negative numbers in an array Problem Statement

Given array contains both positive and negative numbers in random order. We need to rearrange the array elements so that positive and negative numbers are placed alternatively. Number of positive and negative numbers need not be equal. If there are more positive numbers, they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array.

Rearrange Positive and Negative numbers in an array Problem Example

Let the input array be arr[] = {-1, 2, -3, 4, 5, 6, -7, 8, 9}
The output should be arr[] = {9, -7, 8, -3, 5, -1, 2, 4, 6}

Rearrange Positive and Negative numbers in an array Problem Solution

The solution is to first separate positive and negative numbers using partition process of QuickSort. In the partition process, consider 0 as value of pivot element so that all negative numbers are placed before positive numbers. Once negative and positive numbers are separated, we start from the first negative number and first positive number, and swap every alternate negative number with next positive number.

Algorithm:

  1. Use the partition process of quicksort to separate positive and negative numbers.
  2. Consider 0 as the pivot point.
  3. This places all negative numbers before positive numbers.
  4. Start from the first negative number and first positive number
  5. Swap every alternate negative number with next positive number.

How to Rearrange Positive and Negative numbers in an array Problem Solution code in C++

#include <iostream>
using namespace std;

// A utility function to swap two elements
void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
 
/* The main function that rearranges elements of given array. 
  It puts  positive elements at even indexes (0, 2, ..) and 
  negative numbers at odd indexes (1, 3, ..).*/
void rearrange(int arr[], int n)
{
    /* The following few lines are similar to partition process
     of QuickSort.  The idea is to consider 0 as pivot and
      divide the array around it.*/
    int i = -1;
    for (int j = 0; j < n; j++)
    {
        if (arr[j] < 0)
        {
            i++;
            swap(arr[i], arr[j]);
        }
    }
 
    /* Now all positive numbers are at end and negative numbers
     at the beginning of array. Initialize indexes for starting
     point of positive and negative numbers to be swapped*/
    int pos = i+1, neg = 0;
 
    /* Increment the negative index by 2 and positive index by 1,
    i.e., swap every alternate negative number with next 
     positive number*/
    while (pos < n && neg < pos && arr[neg] < 0)
    {
        swap(arr[neg], arr[pos]);
        pos++;
        neg += 2;
    }
}
 

 
// A utility function to print an array
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout<< arr[i]<<" ";
}
 
// Driver program to test above functions
int main()
{
    int arr[] = {-1, 2, -3, 4, 5, 6, -7, 8, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    rearrange(arr, n);
    printArray(arr, n);
    return 0;
}

 Output:

4 -3 5 -1 6 -7 2 8 9

Time Complexity:O(N)
Space Complexity:O(1)

Construct an array from it’s pair sum array

Construct an array from it’s pair sum array

In this post we deal with the problem of constructing the original array from the array in which the sum of all pairs that can be made from the input array are given.

Construct an array from it’s pair sum array Problem Statement:

Given a pair-sum array and size of the original array (n), construct the original array.

A pair-sum array for an array is the array that contains sum of all pairs in ordered form. In general, pair-sum array for arr[0..n-1] is {arr[0]+arr[1], arr[0]+arr[2], ……., arr[1]+arr[2], arr[1]+arr[3], ……., arr[2]+arr[3], arr[2]+arr[4], …., arr[n-2]+arr[n-1}.

Construct an array from it’s pair sum array Problem Example:

Let the Input array be pairsum[] ={8, 12, 6, 10, 4, 8}
The original array will be {5, 3, 7, 1}

Construct an array from it’s pair sum array Problem Solution:

Let the given array be “pairsum[]” and let there be n elements in original array. If we take a look at few examples, we can observe that arr[0] is half of pairsum[0] + pairsum[1] – pairsum[n-1]. Note that the value of pairsum[0] + pairsum[1] – pairsum[n-1] is (arr[0] + arr[1]) + (arr[0] + arr[2]) – (arr[1] + arr[2]).
Once we have evaluated arr[0], we can evaluate other elements by subtracting arr[0]. For example arr[1] can be evaluated by subtracting arr[0] from pairsum[0], arr[2] can be evaluated by subtracting arr[0] from pairsum[1].

Algorithm:

  1. Initialize arr[0] = (pairsum[0]+pairsum[1]-pairsum[n-1]) / 2
  2. Loop from 1 to n(no. of elements in original array)
  3. do arr[i] = pairsum[i-1]-arr[0]

Construct an array from it’s pair sum array Problem Solution Code in C++:

#include <bits/stdc++.h>
using namespace std;

// Fills element in arr[] from its pair sum array pair[]. 
// n is size of arr[]
void constructArr(int arr[], int pairsum[], int n)
{
    arr[0] = (pairsum[0]+pairsum[1]-pairsum[n-1]) / 2;
    for (int i=1; i<n; i++)
        arr[i] = pairsum[i-1]-arr[0];
}
 
// Driver program to test above function
int main()
{
    int pairsum[] = {15, 13, 11, 10, 12, 10, 9, 8, 7, 5};
    int n = 5;
    int arr[n];
    constructArr(arr, pairsum, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Output:

8 7 5 3 2

Time Complexity:O(N)
Space Complexity:O(1)

Swap two given nodes in linked list

Swapping given nodes in linked list

Problem statement for swapping two nodes in linked list:

Given a singly linked list and the data of any two nodes of the linked list, you have to swap the nodes of the linked list without swapping data.

Swap nodes of linked list Example:

Consider a singly linked list
2-> 1-> 4-> 8-> 7-> 9-> 5-> NULL
Data values given: 5, 1
The resultant linked list should be
2-> 5-> 4-> 8-> 7-> 9-> 1-> NULL

Algorithm to swap two nodes of linked list:

Let the data of the nodes to be swapped be n1 and n2. Let curr1 and curr2 point to n1 and n2, respectively.

  1. Check if curr1 and curr2 exist in the given linked list.
    1. If they do, find previous nodes of curr1 and curr2.
    2. Else exit program.
  2. If curr1=curr2, do not swap.
  3. If curr1 =/= curr2, then swap the links of the two nodes.
  4. If one of curr1 or curr2 is the head node, update the head node to curr2 or curr1 accordingly.

Solution code in C++ for swapping given nodes of a linked list:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function that inserts nodes in front of
Given Linked List*/
void InsFront(node **head,int data)
{
   node *temp = new node;
   temp->data = data;
   temp->next = *head;
   *head = temp; 
}

/*Function to swap nodes of given list*/
void Swap_nodes(node **head, int n1, int n2)
{
   node *curr1 = *head;
   node *curr2 = *head;
   node *prev1 = NULL;
   node *prev2 = NULL;
   node *temp;
   
   /*Finds previous node of n1*/
   while(curr1!= NULL && curr1->data != n1)
   {
      prev1 = curr1;
      curr1 = curr1->next;
   }
   
   /*Finds previous node of n2*/
   while(curr2!= NULL && curr2->data != n2)
   {
      prev2 = curr2;
      curr2 = curr2->next;
   }

   if(curr1 == NULL || curr2 == NULL)
   {
      cout<<"\nNode(s) not present in given list.";
      exit(0);
   }

   if(prev1 == prev2)
   {
      cout<<"\nNode can't be swapped with itself.";
      exit(0);
   }

   /*If neither of given nodes
   are the head node of list*/
   if(prev1 && prev2)
   {
      /*Swapping all links*/
      prev1->next = curr2;
      temp = curr2->next;
      curr2->next = curr1->next;
      prev2->next = curr1;
      curr1->next = temp;
   }
   
   /*If curr1 is the head node*/
   else if(prev1 == NULL)
   {
      /*Swapping all links*/
      temp = curr2->next;
      curr2->next = curr1->next;
      prev2->next = curr1;
      curr1->next = temp;
      
      /*Updating head node*/
      *head = curr2;
   }
   
   /*If curr2 is the head node*/
   else if(prev2 == NULL)
   {
      /*Swapping all links*/
      temp = curr1->next;
      curr1->next = curr2->next;
      prev1->next = curr2;
      curr2->next = temp;
   
      /*Updating head node*/
      *head = curr1;
   }
}

/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/* Driver program to test above functions*/
int main()
{
  node* head = NULL;
  InsFront(&head, 5);
  InsFront(&head, 9);
  InsFront(&head, 7);
  InsFront(&head, 8);
  InsFront(&head, 4);
  InsFront(&head, 1);
  InsFront(&head, 2);
  
  cout<<"Created Linked list is:\n";
  printList(head);
  
  /*Calling function to swap nodes*/
  Swap_nodes(&head, 5, 1);
  cout<<"\nResultant Linked list is:\n";
  printList(head);
  
  return 0;
}

Output:

Created Linked list is:
2-> 1-> 4-> 8-> 7-> 9-> 5-> NULL
Resultant Linked list is:
2-> 5-> 4-> 8-> 7-> 9-> 1-> NULL

Time Complexity for swapping given nodes of a linked list: O(N)
where N is the number of nodes in the given linked list.

Swap data of adjacent nodes in a linked list

Pairwise swap data of adjacent nodes in a linked list

Problem statement for swapping data of adjacent nodes in a linked list:

Given a singly linked list, you have to swap the data of adjacent nodes without changing the links between the nodes.

Pairwise swap data of adjacent nodes in a linked list Example:

Consider a singly linked list
3-> 7-> 9-> 2-> 8-> 4-> 1-> NULL
Swapping data of adjacent nodes will result in a linked list
7-> 3-> 2-> 9-> 4-> 8-> 1-> NULL

Solution to swap adjacent nodes of linked list:

Method 1 (Iterative):

Algorithm to iteratively swap data of adjacent nodes of linked list:

  1. Start from the head node.
  2. Swap data of current node with next node.
  3. Move pointer to curr->next->next
  4. Repeat till entire list is traversed.

Solution code in C++ for swapping data of adjacent nodes iteratively:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function that inserts nodes in front of
Given Linked List*/
void InsFront(node **head,int data)
{
   node *temp = new node;
   temp->data = data;
   temp->next = *head;
   *head = temp; 
}

/*Function to swap data of
adjacent nodes of list*/
void Swap_data(node **head)
{
   node *curr = *head;
   int temp;
   
   /*Loop traverses entire list*/
   while(curr!= NULL && curr->next!= NULL)
   {
      /*Swapping data of adjacent nodes*/
      temp = curr->data;
      curr->data = curr->next->data;
      curr->next->data = temp;
      
      /*Updating curr to next alternate node*/
      curr = curr->next->next;
   }
}

/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/* Driver program to test above functions*/
int main()
{
  node* head = NULL;
  InsFront(&head, 1);
  InsFront(&head, 4);
  InsFront(&head, 8);
  InsFront(&head, 2);
  InsFront(&head, 9);
  InsFront(&head, 7);
  InsFront(&head, 3);
  
  cout<<"Created Linked list is:\n";
  printList(head);
  
  /*Calling function to swap data
  of adjacent nodes of list*/
  Swap_data(&head);
  cout<<"\nResultant Linked list is:\n";
  printList(head);
  
  return 0;
}

Output:

Created Linked list is:
3-> 7-> 9-> 2-> 8-> 4-> 1-> NULL
Resultant Linked list is:
7-> 3-> 2-> 9-> 4-> 8-> 1-> NULL

Time Complexity to swap data of adjacent nodes: O(N)
where N is the number of nodes in the linked list.


Method 2 (Recursive):

Algorithm to recursively swap data of adjacent nodes of linked list:

  1. Start from the head node.
  2. Check base case i.e. if head or head->next is NULL then return.
  3. Else, swap data of current node with next node.
  4. Recursively call function for curr->next->next.

Solution code in C++ for swapping data of adjacent nodes recursively:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function that inserts nodes in front of
Given Linked List*/
void InsFront(node **head,int data)
{
   node *temp = new node;
   temp->data = data;
   temp->next = *head;
   *head = temp; 
}
 
/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/*Function to swap data of 
adjacent nodes recursively*/
void Swap_data(node *head)
{
   /*If list has 0 or 1 node*/
   if(head == NULL || head->next == NULL)
      return;
 
   node *curr = head;
   int temp;
 
   /*If there are sufficient nodes in list*/
   if(curr!= NULL && curr->next!= NULL)
   {
      /*Swapping data of adjacent nodes*/
      temp = curr->data;
      curr->data = curr->next->data;
      curr->next->data = temp;
 
      /*Recursively calling function to
      swap data of next pair of nodes*/
      Swap_data(curr->next->next);
   }
}
 
/* Driver program to test above functions*/
int main()
{
  node* head = NULL;
  InsFront(&head, 1);
  InsFront(&head, 4);
  InsFront(&head, 8);
  InsFront(&head, 2);
  InsFront(&head, 9);
  InsFront(&head, 7);
  InsFront(&head, 3);
 
  cout<<"Created Linked list is:\n";
  printList(head);
 
  /*Calling function to swap data
  of adjacent nodes recursively*/
  Swap_data(head);
  
  cout<<"\n";
  printList(head);
  
  return 0;
}

Output:

Created Linked list is:
3-> 7-> 9-> 2-> 8-> 4-> 1-> NULL
Resultant Linked list is:
7-> 3-> 2-> 9-> 4-> 8-> 1-> NULL

Time Complexity to swap data of adjacent nodes: O(N)
where N is the number of nodes in the linked list.

 

Remove duplicates in a Binary Search Tree

Remove duplicate nodes in a Binary Search Tree (BST).

Problem statement to remove redundant nodes in a Binary Search Tree.

Given a binary search tree (BST), remove the redundant nodes to obtain a tree without the duplicate elements.

Example:

INPUT: array: 1,5,8,10,10,12,15,20,20,20
OUTUT:
            10(2)
           /     \
           5      15
         /  \    /  \
        1   8   12   20(3)

Remove duplicates from a Binary Search Tree solution(BST):

Algorithm to remove duplicates :-

  1. Insert elements using inorder traversal.
  2. Increment the count for each node.
  3. If the count is 1,  i.e. the node already exists, then instead of creating a new node, just increment the count.

Solution code in C++ to remove duplicates in a Binary Search Tree(BST):

#include<bits/stdc++.h>
using namespace std;

struct node
{
   int data;
   int count;
   node* left;
   node* right;
};

/*Function to create a new node*/
node* newNode(int key)
{
   node* temp = new node;
   temp->data = key;
   temp->count = 1;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}

/*Function for printing inorder traversal of nodes*/
void Inorder(node *root)
{
   if(!root)
      return;
      
   Inorder(root->left);
   cout << root->data;
   if(root->count > 1)
      cout<<"("<<root->count<<")";
   cout<<" ";
   Inorder(root->right);
}

/*Function to insert nodes in the tree while 
increasing count in case of duplicate elements*/
node* createTree(node* root, int key)
{
   if(!root)
      return newNode(key);
   
   if(key < root->data)
      root->left = createTree(root->left, key);
   
   else if(key > root->data)
      root->right = createTree(root->right, key);
      
   else
   
      (root->count)++;
   
   return root;
}

int main()
{
   /*      10(2)
           /     \
           5      15
         /  \    /  \
        1   8   12   20(3)*/
        
    node *root;
    root = createTree(root,10);
    createTree(root,5);
    createTree(root,15);
    createTree(root,10);
    createTree(root,20);
    createTree(root,20);
    createTree(root,1);
    createTree(root,8);
    createTree(root,12);
    createTree(root,20);
    
    Inorder(root);
    
    return 0;
    
}

Output:

1 5 8 10(2) 12 15 20(3) 

Time Complexity:O(nlogn)

Find number of pairs(x,y) in an array such that x^y > y^x

Find number of pairs(x,y) in an array such that xy > yx

In this post we find solution to the problem of finding number of pairs in the given array such that they satisfy the condition that xy > yx.

Find number of pairs(x,y) in an array such that xy > yx Problem Statement :

Given two integer arrays X[] and Y[], we need to find number of pairs of x,y such that xy > yx where x is an element of array X[] and y is the element of array Y[]. We solve the problem using two methods as described below.

Find number of pairs(x,y) in an array such that xy > yProblem Example:

Input : Let X[] = { 10, 19, 18 } , Y[] = { 11, 15, 9 }
Output : 2
// Two pairs (10,11) and (10,15) exist such that pow(x,y) > pow(y,x)

Find number of pairs(x,y) in an array such that xy > yx Problem Solution :

Method 1:Brute Force

In this brute force solution we consider each element of both arrays, and check whether the given condition satisfies or not.

Algorithm:

  1. Run two loops for both arrays.
  2. The outer loop picks element from array X[].
  3. The inner loop picks element from array Y[].
  4. Check the condition, if satisfied increase count by 1.

Find number of pairs(x,y) in an array such that xy > yx Problem Solution Code in C++ :

#include<bits/stdc++.h>
using namespace std;

/*Function to count pairs following the given condition*/
int CountPairs(int X[], int Y[], int m, int n)
{
 int count = 0;
 for (int i = 0; i < m; ++i)
 {
    for (int j = 0; j < n; ++j)
    {
       /*Checking condition for each pair*/
       if (pow(X[i], Y[j]) > (pow(Y[j],X[i])))
       {
         /*Incrementing count if condition true*/
          count++;
       }
    }
 }
 return count;
}

/*Driver function to test above function*/
int main()
{
 int X[] = { 2, 1, 6 };
 int Y[] = { 1, 5 };

 int m = sizeof(X)/sizeof(X[0]);
 int n = sizeof(Y)/sizeof(Y[0]);

 cout<<"Total Pairs = "<<CountPairs(X,Y,m,n);

 return 0;
}

Output:

 Total Pairs = 3

Time Complexity:O(m+n)
Space Complexity:O(1)


Method 2:

In this method we solve the problem by first sorting the array Y[]. The approach used here is that if y > x then xy > yx

.

Algorithm:

  1. Sort the array Y[].
  2. For every x in X[], find the index(id) of smallest no. greater than x(ceil of x) in Y[].
  3. All the numbers after id satisfy the relation so just add (n-idx) to the count.

 Solution Explanation:

Let the input arrays be
X[] = {10, 19, 18 }
Y[] = {4, 11, 15, 9 }

  1. Step 1: Y[] = {4, 9, 11, 15 }
  2. Step 2: id = 2 //
    for X[0] = 10, we find id = 2(as ceil of x is 11 which is Y[2]), count = 0+(4-2)
    for X[1] = 19, no such id in Y, no change in count.
    for X[2] = 18, no such id in Y, no change in count.

Find number of pairs(x,y) in an array such that xy > yx Problem Solution Code in C++ :

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;

/* This function return count of pairs with x as one element
     of the pair. It mainly looks for all values in Y[] where
       x ^ Y[i] > Y[i] ^ x*/
int count(int x, int Y[], int n, int NoOfY[])
{
    /* If x is 0, then there cannot be any value in Y
        such that x^Y[i] > Y[i]^x*/
    if (x == 0) return 0;

    /* If x is 1, then the number of pairs is equal to number of
         zeroes in Y[]*/
    if (x == 1) return NoOfY[0];

    /* Find number of elements in Y[] with values greater than x
      upper_bound() gets address of first greater element in Y*/
    int* id = upper_bound(Y, Y + n, x);
    int ans = (Y + n) - id;

    /* If we have reached here, then x must be greater than 1,
        increase number of pairs for y=0 and y=1*/
    ans += (NoOfY[0] + NoOfY[1]);

    /* Decrease number of pairs for x=2 and (y=4 or y=3)*/
    if (x == 2)  ans -= (NoOfY[3] + NoOfY[4]);

    /* Increase number of pairs for x=3 and y=2*/
    if (x == 3)  ans += NoOfY[2];

    return ans;
}

/* The main function that returns count of pairs (x, y) such that
   x belongs to X[], y belongs to Y[] and x^y > y^x*/
int countPairs(int X[], int Y[], int m, int n)
{
    // To store counts of 0, 1, 2, 3 and 4 in array Y
    int NoOfY[5] = {0};
    for (int i = 0; i < n; i++)
        if (Y[i] < 5)
            NoOfY[Y[i]]++;

    // Sort Y[] so that we can do binary search in it
    sort(Y, Y + n);

    int total_pairs = 0; // Initialize result

    // Take every element of X and count pairs with it
    for (int i=0; i<m; i++)
        total_pairs += count(X[i], Y, n, NoOfY);

    return total_pairs;
}

// Driver program to test above functions
int main()
{
    int X[] = {2, 1, 6};
    int Y[] = {1, 5};

    int m = sizeof(X)/sizeof(X[0]);
    int n = sizeof(Y)/sizeof(Y[0]);

    cout << "Total pairs = " << countPairs(X, Y, m, n);

    return 0;
}

Output:

 Total pairs = 3

Time Complexity:O(n logn + m logn)
Space Complexity:O(1) 

Delete an Array Element(using one and two traversals)

Delete an Array Element

In this post we deal with the common problem of deleting an element fro the array using not only two but one traversal too.

Delete an Array Element Problem Statement:

Given an array of n integers ,we need to delete a given element of the array. We can delete an array element using two and one traversals of the array.

Delete an Array Element Problem Example:

Let the input array be arr[] = { 4, 7, 1, 9, 2 , 5}
let x = 2
Output array arr[] = {4, 7, 1, 9, 5 }

Delete an Array Element Problem Solution:

Method 1: Using two traversals

In this method we first search the element in the array and then shift the elements on the right of ‘x’ one place back.

Algorithm

  1. Search for ‘x’ using linear search.
  2. Shift elements on the right of ‘x’ to one place back.

Delete an Array Element Problem Solution Code in C++:

#include <bits/stdc++.h>
using namespace std;

/* This function removes an element x from arr[] and
   returns new size after removal (size is reduced only
     when x is present in arr[]*/
int deleteElement(int arr[], int n, int x)
{
   // Search x in array
   int i;
   for (i=0; i<n; i++)
      if (arr[i] == x)
         break;
 
   // If x found in array
   if (i < n)
   {
     /* reduce size of array and move all
        elements on space ahead*/
     n = n - 1;
     for (int j=i; j<n; j++)
        arr[j] = arr[j+1];
   }
 
   return n;
}
 
/* Driver program to test above function */
int main()
{
    int arr[] = {11, 15, 6, 8, 9, 10};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 6;
 
    // Delete x from arr[]
    n = deleteElement(arr, n, x);
 
    cout << "Modified array is \n";
    for (int i=0; i<n; i++)
       cout << arr[i] << " ";
 
    return 0;
}

Output:

Modified array is 
11 15 8 9 10

Time Complexity:O(N)
Space Complexity:O(1)


Method 2:  Using one Traversal

In this method we make an assumption that the element given in the question is always present in the array. We start from the rightmost element, search for the element and update the array if not found.

Algorithm:

  1. Traverse the array from the rightmost element.
  2. Keep shifting the elements one place back untill ‘x’ is found.

Delete an Array Element solution code in C++:

#include <bits/stdc++.h>
using namespace std;

/* This function removes an element x from arr[] and
   returns new size after removal.Otherwise 0
     is returned to indicate failure.*/
int deleteElement(int arr[], int n, int x)
{
   // If x is last element, nothing to do
   if (arr[n-1] == x)
       return (n-1);
 
   /*Start from rightmost element and keep moving
       elements one position ahead.*/
   int prev = arr[n-1], i;
   for (i=n-2; i>=0 && arr[i]!=x; i--)
   {
       int curr = arr[i];
       arr[i] = prev;
       prev = curr;
   }
 
   // If element was not found
   if (i < 0)
     return 0;
 
   // Else move the next element in place of x
   arr[i] = prev;
 
   return (n-1);
}
 
/* Driver program to test above function */
int main()
{
    int arr[] = {11, 15, 6, 8, 9, 10};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 6;
 
    // Delete x from arr[]
    n = deleteElement(arr, n, x);
 
    cout << "Modified array is \n";
    for (int i=0; i<n; i++)
       cout << arr[i] << " ";
 
    return 0;
}

 Output:

Modified array is 
11 15 8 9 10

Time Complexity:O(N)
Space Complexity:O(1)

Note: This approach may give unexpected result when ‘x’ is not present