Interview Question #8

The below is the method I wrote in the interview panel, but this will be best method only if the given number's index is equal or greater than half of the array's size. If the given number lies first half of the array size, we need to count all the numbers greater than given number k in the big array which is costly and time consuming.

#include <stdio.h>
#define ARR_SIZE 10

int count_largest(int arr[], int size, int k)
{
   int i, j, l = 0, flag = 0, count = 0, start = 0, end = size-1, pivot = size/2;
   int digits[ARR_SIZE] = {0};   

   if (arr[pivot] > k) {
       end = pivot - 1;
   } else {
       start = pivot + 1;
   }
   printf("The largest number greater than %d in the arr are ", k);
   for (l = start, i = start; i < size; i++) {
       for (j = start; j < size; j++) {
           if (digits[j] == arr[i]) {
              flag = 1;
              break;
           } 
       }
       if ((flag != 1) && (arr[i]) > k) {       
           digits[l++] = arr[i];
           printf("%d ",arr[i]);
           count++;
       } 
       flag = 0;
     
   }
   return count;
}

int main()
{
   int arr[ARR_SIZE] = {1, 2, 3, 3, 4, 5, 10, 11, 11, 13};
   int count = 0;
   count = count_largest(arr, ARR_SIZE, arr[5]);
   printf("\nThe number of elements > 5 are %d\n", count);
   return 1;
}

Output:

The largest number greater than 5 in the arr are 10 11 13 The number of elements > 5 are 3

Since it is sorted, you can go for hashing or binary search algorithm. <Will be updated>



Please leave a comment if anything is wrong.