CODEWITHSUNDEEP
arraysalgorithmsumbig-o
Bartlomiej Lewandowski
Bartlomiej Lewandowski

Reputation: 11190

Algorithm - Find the center index

Given an array of ints with size t, one needs to find the center index. The center index x is the index where the sum of ints (0 to x-1) is equal to sum (x+1 to t-1).

The best algorithm I could come up with is O(n).

I would have a temp array with the sums of all ints before (not including the one at index x) : so at index 1 it would be 1, at 2 it would be a sum of 2 and 1 and so on.

Another int would be the sum of all ints.

I would loop twice through the array, the first make the temp array, and the other to find if both parts are equal.

Is there a better algorithm O(logn)?

Upvotes: 2

Views: 393

Answers (1)

P.P
P.P

Reputation: 121407

Since you have to calculate the sum of both the half of the array, this can't be solved in less than O(n). Because you have to inspect each element at least once (to calculate the sum). Any algorithm can be logn only if we can skip inspecting certain elements of the array based on some condition which is not possible here.

Upvotes: 3

Related Questions