Sunday, March 29, 2015

Find popular items


Find popular item in sorted array of natural numbers.
An item is popular is if its repeated n/4 times or more.
For Ex:
Input: 123444445678
Popular item is 4.
Liner scan is O(n), but solution needs to be in O(logN) complexity and O(1) space complexity.

This is actually a very interesting problem. Since the popular item is defined as the element is repeated more than 1 / 4 times, and since it is a sorted array, so it can only occurs on 0, n / 4, n /2 and 3n/4 index. And the rest is just do binary search and get the range.


public class PopularNumber {
 public static void popular(int[] n){
  if(n == null || n.length == 0)
   return;
  int len = n.length;
  int[] check = {0, len / 4, len / 2, 3 * len / 4};
  for(int i = 0; i < 4; i++){
   if(i > 0 && n[check[i]] == n[check[i - 1]])
    continue;
   int l = check[i];
   int start = binarySearchStart(n, n[l]);
   int end = binarySearchEnd(n, n[l]);
   //need to be larger than the ceil in case len / 4.0 is not an integer
   if(end - start + 1 >= Math.ceil(len / 4.0))
    System.out.println(n[l]);
  }
 }
 private static int binarySearchEnd(int[] n, int target){
  int len = n.length;
  int start = 0;
  int end = len - 1;
  while(start + 1 < end){
   int mid = (start + end) / 2;
   if(n[mid] <= target)
    start = mid;
   else
    end = mid;
  }
  if(n[end] == target)
   return end;
  else return start;
 }
 private static int binarySearchStart(int[] n, int target){
  int len = n.length;
  int start = 0;
  int end = len - 1;
  while(start + 1 < end){
   int mid = (start + end) / 2;
   if(n[mid] >= target)
    end = mid;
   else
    start = mid;
  }
  if(n[start] == target)
   return start;
  else
   return end;
 }

 public static void main(String[] args) {
  //int[] n = {1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8};
  int[] n = {1, 1, 2, 3, 4};
  popular(n);
 }
}

No comments:

Post a Comment