Count frequency of a number in a sorted array
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
Find popular element in an array
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 […]
Divide & Conquer Approach to find a^n
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 […]
