CODEWITHSUNDEEP
arraysalgorithmdata-structures
Hey.Its_RJ
Hey.Its_RJ

Reputation: 125

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

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?

Upvotes: 4

Views: 1483

Answers (2)

Abhinav Mathur
Abhinav Mathur

Reputation: 8196

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)

Upvotes: 9

Prajwal Mathad
Prajwal Mathad

Reputation: 1

Based on the recommended answer, How can you get to know the count of each element in the array? My understanding is, the binary search will give you the first occurrence of that element, but you still need to know the elements greater or lesser than that to count the occurrence and in doing so you will still traverse the whole array, resulting in O(N). Correct me if I am wrong.

Upvotes: 0

Related Questions