CODEWITHSUNDEEP
algorithmarray-algorithms
Maxwell Newberry
Maxwell Newberry

Reputation: 29

Finding sum of distance from current index to all other indexes

Given an array arr(0, 0, 1, 1, 1) for example, I need to find the sum of the distance from all other indexes to the current index if the value is 1. For example, I have the following code in O(n^2) notation, but I know that I can probably do it in O(n).

arr = [0, 1, 1, 1, 1]
for(i = 0; i < arr.length; i++) {
   sum = 0;
   for(j = 0; j < arr.length; j++) {
      if(arr[j] == 1 && j != i) {
         sum += Math.abs(j - i);
      }
   }
   return_arr[i] = sum;
}

(Not in any specific language)

Distance is denoted in the absolute value of j - i.

Upvotes: 0

Views: 114

Answers (1)

SomeDude
SomeDude

Reputation: 14238

Irrespective of the value is 1 or not, the number of values to the left of any index i is i and the number of values to the right of it is n-1-i where n is the length of the array.

And you know that sum of first n natural numbers i.e. 1, 2, 3, ... n is n(n+1)/2

You do the sum for the number of indices to the left = i(i+1)/2

Sum for the number of indices to the right = (n-i-1)(n-i)/2

Add both sums to get sum for one index = i(i+1)/2 + (n-i-1)(n-i)/2

Do that at each index whose value is 1.

Pseudo code:

GetSumAtEachIndex(arr) {
    n = arr.length
    sum = array(n)
    for ( i = 0; i < arr.length; i++ ) {
        if ( arr[i] == 1 ) {
           sum[i] = i*(i+1)/2 + (n-i-1)*(n-i)/2;
        }
    }
    return sum;
}

Upvotes: 2

Related Questions