Given a sorted array of numbers and a number x, count the number of occurrences of x in the array.

Input:

int arr[] = {1, 3, 3, 4, 4 ,5, 5, 5, 7, 8, 8}; int x = 5; Output: 3

May 262017

Given a sorted array of numbers and a number x, count the number of occurrences of x in the array.

Input:

int arr[] = {1, 3, 3, 4, 4 ,5, 5, 5, 7, 8, 8}; int x = 5; Output: 3

Mar 102015

Given a sorted array of integers, find a “popular” element i.e. one which occurs more than n/4 times. If no such element exist (which occurs more than n/4 times) then print error.

For example: If Input array has 8 elements as below {1, 3, 3, 3, 4, 6, 9, 10} Then 3 is the popular element that comes three times.

Jun 132012

If you want to compute a^n ( a raised to the power n), then the algorithm is simple:

long power(int a, int n) { long prod = 1, i=0; for(; i<n; i++) prod = prod * a; return prod; }

But the above function will take O(n) time.

Write a divide & conquer algorithm which takes O(lg(n)) time to compute **a ^{n}**. Continue reading »