Interview Question for Intern at Google:

O(logN) required

Use binary search to find the number (O(logN)). Once that is done you can search around that index. Though that could become O(N).

Better answer: run binary search again twice once you have found the number the first time. For the upper half and the lower half - so total run time is O(logN)

I think it is not possible in O(logN) because anyway traversing the complete array is needed to access all the numbers. Worst Case scenario would be the last number repeating itself 5 times. For example : {1,2,2,3,3,3,4,4,4,4,5,5,5,5,5} and if you are asked to find out the occurrences of number '5' then you have to traverse the complete array once which means the complexity should be O(N).

JAVA Code : // For Sorted and UnSorted Array in O(N) time Complexity.

import java.util.HashMap;

public class FindOccurrences {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int unsortedArray[] = {4,6,7,8,4,5,6,8,3,2,4,5,7,8,9,3,4,6,7,8};
        System.out.println(findOccurrencesUnsorted(unsortedArray,8));

        int sortedArray[] = {1,2,2,3,3,3,4,4,4,4,5,5,5,5,5};
        System.out.println(findOccurrencesSorted(sortedArray,5));
    }

    private static int findOccurrencesUnsorted(int[] array, int number)
    {
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<array.length;i++)
        {
            if(map.get(array[i])==null)
                map.put(array[i],1);
            else
            {
                int count = map.get(array[i]);
                count++;
                map.remove(array[i]);
                map.put(array[i],count);
            }
        }
        return map.get(number);
    }

    private static int findOccurrencesSorted(int[] array, int number)
    {
        int counter = 0;
        for(int i=0;i<array.length;i++)
        {
            if(array[i]!=number)
                continue;
            else
            counter++;
        }
        return counter;
    }
}