Monday, 6 March 2017

C++ Program to find First and Last occurrence of an x

This question has been already appeared in the interviews of following companies:

Linkedin, Amazon

Source : geeksforgeeks

In the question you have given a sorted array with possibly duplicate elements, the taks is to find the indexes of first and last occurrences of an element x in the given array.

Example:
  
       Input: A[] ={1, 3, 5, 5, 5, 5, 67, 123, 125 }
                 x=5
       Output:   First Occurrence = 2
                     Last Occurrence = 5

Input: 
In the input first line will contain t denoting the number of test cases. Then T test cases follow. Each test case contains an integer N denoting the number of elements in the array . Then in the next line there are N space separated values of the array. The last element of each test case contains an integer whose indexes you have to found:

Output: You have to print the First and last occurrence of the element, But if the element is not present in the array then print -1.

Solution:

Approach is simple. First we will check that element is present or not in the array by using binary search. If the element is present then we call two separate methodes minindex() and maxindex() which will perform binary search and will return minimum index (First occurrence) and maximum index (Last occurrence) of x respectievely.

C++ Program to find First and Last occurence of x is given below.


#include <stdio.h>
int minindex(int x);
int maxindex(int x);
int arr[100],n;
bool check(int x);
int main()
{
      int i,min_index,max_index,x;
      int t,j;
      printf("\nEnter the number of test cases: ");
      scanf("%d",&t);
      for(i=0;i<t;i++)
      {
            printf("\n\nEnter the number of elements in %d test case: ",i+1);
            scanf("%d",&n);
            printf("\nEnter the elements: \n");
            for(j=0;j<n;j++)
            {
                  scanf("%d",&arr[j]);
            }
            printf("\nEnter the element x whose index you have to found: ");
            scanf("%d",&x);
            if(check(x))
            {
                  min_index=minindex(x);
                  max_index=maxindex(x);
                  printf("%d %d",min_index,max_index);
            }
            else
            {
                  printf("-1");
            }
            printf("\n");
      }
      return 0;
}
bool check(int x)
{
     int beg,mid,end;
     beg=0;
     end=n-1;
     if(x<arr[beg] && x>arr[end])
     {
          return false;
     }
     else
     {
           mid=(beg+end)/2;
           while(beg<=end)
           {
                  if(arr[mid]==x)
                  {
                        return true;
                  }
                  else
                  {
                        if(arr[mid]>x)
                        {
                             end=mid-1;
                        }
                        else
                        {
                             beg=mid+1;
                        }
                        mid=(beg+end)/2;
                  }
          }
          return false;
     }
}
int minindex(int x)
{
    int beg,end,mid;
    beg=0;
    end=n-1;
    mid=(beg+end)/2;
    while(beg<=end)
    {
        if(x==arr[mid] && x>arr[mid-1])
        {
            return mid;
        }
        else
        {
              if(x<=arr[mid])
              {
                    end=mid-1;
              }
              else
              {
                    beg=mid+1;
              }
              mid=(beg+end)/2;
        }
    }
    return -1;
}
int maxindex(int x)
{
      int beg,mid,end;
      beg=0;
      end=n-1;
      mid=(beg+end)/2;
      while(beg<=end)
      {
             if(x==arr[mid] && x<arr[mid+1])
             {
                   return mid;
             }
             else
             {
                   if(x<arr[mid])
                   {
                         end=mid-1;
                   }
                   else
                   {
                         beg=mid+1;
                   }
                   mid=(beg+end)/2;
             }
      }
}


OUTPUT:

 


EmoticonEmoticon