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?

CodePudding user response：

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.