Hackerrank The subarray sums question - time out test cases

As suggested by @Annity, you need to maintain two arrays:

1. Sum of all numbers so far. At any point of the index, it should have the sum of all previous numbers.
2. Same as above but it should have the total count of all previous Zeros.

You should avoid nested loops to reduce time complexity. Here is a solution in javascript:

function  findSum(numbers,  queries)  {

  let  result  =   [];    
  let  subArraySum  =   [];    
  let  countZero  =  numbers[0]  ==  0  ?  1  :  0;    
  let  zeroArr  =   [];    
  zeroArr[0] =  countZero;    
  subArraySum[0]  =  numbers[0];    
  for (let  i = 1;  i <=  numbers.length - 1;  i++)  {               
    if (numbers[i]  ==  0) {            
      countZero++;            
      zeroArr[i]  =  countZero;        
    } 
    else  {            
      zeroArr[i]  =  countZero;         
    }         
    subArraySum[i]  = subArraySum[i - 1]  +  numbers[i];    
  }    

  for (let  q  of  queries)  {            
    if (q.length  ==  3)  {            
      let  i  =  q[0];            
      let  j  =  q[1];            
      let  x  =  q[2];            
      let  sum  =  0;                       
      sum  =  subArraySum[j - 1] - ((i - 2  <  0 )  ?  0  :  subArraySum[i - 2]);             
      sum  =  sum  +  (zeroArr[j - 1] - ((i - 2  <  0 )  ?  0  :  zeroArr[i - 2])) * x;            
      result.push(sum);        
    }                  
  }    
  return  result;
}
console.log(findSum([5, 10, 15], [
  [1, 2, 5]
]))
console.log(findSum([0, 10, 15], [
  [1, 2, 5]
]))

Here's the solution that occurred to me.

You need to create two new arrays - one for the sums and one for the number of zeroes. Eg. sums[] and zeroes[].

In these two arrays you will store the value for the sum and the number of zeroes from the first element to the current. This is how it goes:

Loop through all of the numbers.

For each number with index i save in sums[i] the cumulative sum of all the elements from the first to the current and in zeroes[i] - the number of zeroes from the first element to the current.

Then loop through all of the queries.

For every query calculate the sum:

You take the sum from the sums array for the element with the right index and deduct the sum for the element before the left index. (sum = sums[r] - sums[l-1])

If you deduct the count of zeroes in the element before the left index from the number in the element on the right index - you will get the number of zeroes in the interval. (zero = zeroes[r] - zeroes[l-1])

Then multiply it by the third element in the query and add it to the sum.

And this is how you have the sum for the query.

Your code takes a linear time per query. Invest in a linear time once to precompute an array of partial sums. Then each query will be answered in a constant time.

public static List<Long> findSum(List<Integer> numbers, List<List<Integer>> queries) {
    // Write your code here
    ArrayList<Long> arr = new ArrayList<>();

    for(int i = 0; i < queries.size(); i++) {
        int sum = 0;

        for(int j = queries.get(i).get(0) - 1; j <= queries.get(i).get(1) - 1; j++) {
            if(numbers.get(j) == 0){
                sum += queries.get(i).get(2);
            } else {
                sum += numbers.get(j);
            }
        }

        arr.add((long)sum);
        sum = 0;
    }

    return arr;
}

The logic tries to sum each index with the last index. But initializes the first index with 0. The same with counting the zero. After that, just subtract the left side with the desired index. Also with the zero value in the index, but multiplid by the queries. There you have it. I can't post the answer.

this is in python

tempRes=0
    temp = []
    for b in range(len(queries)):
        for k in range(queries[b][0]-1,queries[b][1]):
            if numbers[k] == 0:
                tempRes = tempRes + queries[b][2]
            tempRes = tempRes + numbers[k]
        temp.append(tempRes)
        tempRes = 0
        

    return temp

Try this(in javascript):

function findSum(numbers, queries) {
  // Write your code here
  let sumArr = [];

  for (let i = 0; i < queries.length; i++) {
    let sum = 0;
    let start = queries[i][0];
    let end = queries[i][1] + 1;
    let x = queries[i][2];

    const newArr = numbers.slice(start, end);

    newArr.forEach((item) => {
      if (item === 0) {
        sum = sum + x;
      }
      sum = sum + item;
    });
    sumArr.push(sum);
  }
  return sumArr;
}

#!/usr/bin/python3


def solution(numbers, queries):
    if not isinstance(numbers, list) and not isinstance(queries, list):
        return
    result = []
    total = 0
    for query in queries:
        if len(query) == 3:
            start = query[0]
            end = query[1]
            additional = query[2]
            selection = numbers[start-1:end]
            has_zeros = False
            for el in selection:
                if el == 0:
                    has_zeros = True
            print(f"has_zeros: {has_zeros}")
            print(f"selection: {selection}")
            total = sum(selection)
            if has_zeros:
                total += additional
            result.append(total)
    return result


if "__main__" == __name__:
    # 15
    _input = [5, 10, 10]
    _queries = [[1], [3], [1, 2, 5]]
    print(f"input: {_input}")
    print(f"queries: {_queries}")
    _output = solution(_input, _queries)
    print(f"ouput: {_output}")

Solution in python3 :

def findSum(numbers, queries):
    a = [0]
    b = [0]
    for x in numbers:
        a.append(a[-1] + x)
        b.append(b[-1] + (x == 0)) if in subarray has 0, sum = sum + number x)
    return [a[r] - a[l - 1] + x * (b[r] - b[l - 1]) for l, r, x in queries]