Saturday, 11 March 2017

Find the type of array

Given an array, it can be of 4 types
(a) Ascending
(b) Descending
(c) Ascending Rotated
(d) Descending Rotated
Find out which kind of array it is and return the maximum of that array.

// C++ program to find type of array, ascending
// descending, clockwise rotated or anti-clockwise
// rotated.
#include<bits/stdc++.h>
using namespace std;

// Function to find the type of an array
// and maximum element in it.
void findType( int arr[] , int n)
{

    // boolean variables to check if array is increasing or decreasing
    bool isIncreasing = false , isDecreasing = false;
for( int i = 1 ; i < n ; ++i){
   
   // increasing value found
   if(arr[i-1] < arr[i]){
       isIncreasing = true;
       // if the array was decreasing earlier then its Descending Ascending and maximum is current element
       // example :  2 1 5 4 3 
       if(isDecreasing){
           cout << "Descending rotated Max : " << arr[i] << "\n";
           return;
       }
   }
    // decreasing value found
   else if (arr[i-1] > arr[i]){
       isDecreasing = true;
        // if the array was increasing earlier then its Ascending Descending and maximum is i-1 element
        // eg 4 5 1 2 3
       if(isIncreasing){
           cout << "Ascending rotated Max : " << arr[i-1] << "\n";
           return;
       }
       
   }
   
}

// else array is purely ascending or descending
if(isIncreasing)
    cout << "Ascending  Max : " << arr[n-1] << "\n";
else
   cout <<"Descedning Max : " << arr[0] << "\n";

}

// Driver code
int main()
{
int arr1[] = { 4, 5, 6, 1, 2, 3}; // Ascending rotated
int n = sizeof (arr1) / sizeof (arr1[0]);
findType(arr1, n);

int arr2[] = { 2, 1, 7, 5, 4, 3}; // Descending rotated
n = sizeof(arr2) / sizeof (arr2[0]);
findType(arr2, n);

int arr3[] = { 1, 2, 3, 4, 5, 8}; // Ascending
n = sizeof(arr3) / sizeof (arr3[0]);
findType(arr3, n);

int arr4[] = { 9, 5, 4, 3, 2, 1}; // Descending
n = sizeof(arr4) / sizeof (arr4[0]);
findType(arr4, n);

return 0;
}