Find number of Rotation
PROBLEM :
Given a sorted array which is rotated 'N' times. Find the value of 'N'.
Input:
The first line contains an integer T, depicting total number of test cases.
Then following T lines contains an integer N depicting the size of array and next line followed by the value of array.
Output:
Print the value of 'n'.
Constraints:
1 = T = 40
1 = N = 100
0 = A[i] = 100
Example:
Input
2
5
5 1 2 3 4
5
1 2 3 4 5
Output
1
0
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<iostream>
using namespace std;
int Rotation(int [],int ) ;
int main()
{
int t,arr[100],i,no ;
cin>>t ;
while(t--)
{
cin>>no ;
for(i=0;i<no;i++)
cin>>arr[i] ;
no=Rotation(arr,no) ;
cout<<no<<endl ;
}
return 0;
}
int Rotation(int arr[],int no)
{
int i,min,count ;
min=arr[0] ;
count=0 ;
for(i=0;i<no;i++)
{
if(min>=arr[i])
{
if(arr[i]!=arr[i-1])
count=i ;
min=arr[i] ;
}
}
return count ;
}
---------------------------------------------------------------------------------
Given a sorted array which is rotated 'N' times. Find the value of 'N'.
Input:
The first line contains an integer T, depicting total number of test cases.
Then following T lines contains an integer N depicting the size of array and next line followed by the value of array.
Output:
Print the value of 'n'.
Constraints:
1 = T = 40
1 = N = 100
0 = A[i] = 100
Example:
Input
2
5
5 1 2 3 4
5
1 2 3 4 5
Output
1
0
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<iostream>
using namespace std;
int Rotation(int [],int ) ;
int main()
{
int t,arr[100],i,no ;
cin>>t ;
while(t--)
{
cin>>no ;
for(i=0;i<no;i++)
cin>>arr[i] ;
no=Rotation(arr,no) ;
cout<<no<<endl ;
}
return 0;
}
int Rotation(int arr[],int no)
{
int i,min,count ;
min=arr[0] ;
count=0 ;
for(i=0;i<no;i++)
{
if(min>=arr[i])
{
if(arr[i]!=arr[i-1])
count=i ;
min=arr[i] ;
}
}
return count ;
}
---------------------------------------------------------------------------------
Comments
Post a Comment