• • Write a C program to find turning number in an array. The problem is an interview questions. You have to find maximum number which increases at a certain index in an array and immediately decreases.

For example if the given array is {1, 2, 3, 4, 11, 8, 7, 6} , the turning number is 11. In Another example {1, 2, 3, 4, 11, 8, 7, 6,9,10,11,12,3,4} turning number is 12.

## C program to Find Turning Number in an Array

```#include <stdio.h>

int findTurningNumber(int *arr, int size)
{
int i;
int maximum = 0;
for (i = 0; i < size; i++)
{
if (arr[i] > arr[i+1])
{
if( arr[i] > maximum)
maximum = arr[i];
}
}
return maximum;
}

int arr[] = {1, 2, 3, 4, 11, 8, 7, 6,9,10,11,12,3,4};

int main()
{
int size = sizeof(arr)/sizeof(arr);
printf("The turning number is %d\n", findTurningNumber(arr, size));
return 0;
}
```

## Compile and run on Linux

```bosch@bosch-Inspiron-N5050:~/myproject/sample\$ gcc turning.c -o turning
bosch@bosch-Inspiron-N5050:~/myproject/sample\$ ./turning
The turning number is 12
```

The above implementation has time complexity : O(n)

### More efficient way to write C program to Find Turning Number in an Array

The above solution can be modified to reduce time complexity of O(n) to time complexity of O(logn).

```#include <stdio.h>
#include<limits.h>

int max = INT_MIN;

void findTurningNumber(int arr[], int start, int end) {

// recursion end condition
if (start == end) {
return;
}

if ((start == end - 1) && arr[start] >= arr[end] && max < arr[start]) {
max = arr[start];
}

if ((start == end -1) && arr[start] < arr[end] && max < arr[end]) {
max = arr[end];
}

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

if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1])
findTurningNumber(arr, start, mid - 1);
else
findTurningNumber(arr, mid + 1, end);
}

int arr[] = { 1, 2, 3, 4, 9, 8, 7, 6, 9, 10, 11, 12, 3, 4 };

int main() {
int size = sizeof(arr) / sizeof(arr);
findTurningNumber(arr, 0, size);
printf("The turning number is %d\n", max);
return 0;
}
```

Ref:

https://gist.github.com/luckypapa/2240d5839795d380b1df