Showing posts with label Arrays. Show all posts
Showing posts with label Arrays. Show all posts

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;
}