Finding Number

PROBLEM :

An array is bitonic if it is comprises of an increasing sequence of integers followed immediately by a decreasing sequence of integers.
Given such a array, you need to find a element X in it and print its index.
In case, X does not exist in the array print "OOPS! NOT FOUND" without quotes.
Note: It is guaranteed that array consist of distinct elements. And array indexing is from 0.

Input:
First line will consist  a number T, the number of test cases.
Each test case will then consist of two numbers N and X. N being the array size and X being the element to be searched for.
Next line will consist of N space separated integers.

Output:
Print the required answer on separate lines.

Constraints:
1<=T<=10
1<=N<=200
-100<=A[i]<=100

Example:
INPUT
1
5 2
1 2 7 4 3

OUTPUT
1

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;

int FindingNumber(int [],int ,int ) ;
int FindPivot(int [],int ,int ) ;
int FindNumber(int [],int ,int ,int ) ;

int main()
{
int t ;
cin>>t ;
while(t--)
{
   int no,k ;
   cin>>no>>k ;
 
   int arr[no] ;
   for(int i=0;i<no;i++)
       cin>>arr[i] ;
     
   no=FindingNumber(arr,no,k) ;
 
   if(no==-1)
       cout<<"OOPS! NOT FOUND" ;
   else
       cout<<no ;
   cout<<endl ;
}
return 0;
}

int FindingNumber(int arr[],int no,int k)
{
    int pivot=FindPivot(arr,0,no-1) ;
   
    if(pivot==-1)
        return FindNumber(arr,0,no-1,k) ;
       
    if(arr[pivot]==k)
        return pivot ;
       
    if(arr[0]<=k)
        return FindNumber(arr,0,pivot-1,k) ;
       
    else
        return FindNumber(arr,pivot+1,no-1,k) ;
}

int FindPivot(int arr[],int start,int end)
{
    if(start>end)
        return -1 ;
       
    if(start==end)
        return start ;
       
    int mid=(start+end)/2 ;
   
    if(mid<end&&arr[mid]>arr[mid+1])
        return mid ;
       
    else if(mid>start&&arr[mid]<arr[mid-1])
        return mid-1 ;
       
    else if(arr[start]>=arr[mid])
        return FindPivot(arr,start,mid-1) ;
       
    else
        return FindPivot(arr,mid+1,end) ;
}

int FindNumber(int arr[],int start,int end,int k)
{
    if(start>end)
        return -1 ;
       
    int mid=(start+end)/2 ;
   
    if(arr[mid]==k)
        return mid ;
       
    else if(arr[mid]<k)
        return FindNumber(arr,mid+1,end,k) ;
   
    else
        return FindNumber(arr,start,mid-1,k) ;
}

--------------------------------------------------------------------------------

Comments

Popular posts from this blog

Count ways to N'th Stair(Order does not matter)

Replace all ‘0’ with ‘5’ in an input Integer

Chocolate Distribution Problem

Remove characters from the first string which are present in the second string

Primality Test ( CodeChef Problem code: PRB01 )