Finding sum of a sorted array in O(log n) Time Complexity

Question

There is a Sorted Array A[1,..,n] where each element in the array is between [0-9] and numbers can be repeated with conditions i.e. A[i] <= A[i+1] (less than equal to)

Is there any way to compute this in O(log n) time complexity?

Answer 1

Use binary search to find the first occurrence of 0, then the first occurrence of 1, and so on all the way up to 9. That way, you'll know the exact count of 0's, 1's, 2's.. etc in the array.

Array sum = (1's count*1) + (2's count * 2) ... (9's count * 9).

Total complexity = O(logN) for running binary search 9 times.

Edit:

Count of x in the array will be

If `x` isn't the largest element
count(x) = (first index of the next greatest number) - (first index of x)

Else
count(x) = length of array - (first index of x)