Sum of n number inside array is x number and create subset of result

13
May 15, 2019, at 10:10 PM

For example, if you have an array [20, 6, 7, 8, 50] and if I pass value 21 it should return [6,7,8] this sub array. Note: the sum of number should be in sequence.

[20, 6, 7, 8, 50]
21 - [6, 7, 8]
13 - [6, 7]
50 - [] - because it is not in sequence

I tried but not working

function sumoftwonumer(arr, s) {
    let hashtable = {}
    let sum = []
    for(let i=0; i<arr.length; i++) {
        let innerRequiredValue = s - arr[i] 
        if(hashtable[innerRequiredValue.toString()] !== undefined) {
            sum.push([arr[i], innerRequiredValue])
        }
        hashtable[innerRequiredValue.toString()] = arr[i]
    }
    console.log(hashtable)
    return sum
}
Answer 1

You can try using nested for loop. The time complexity in worst case will O(n^2). Make sure to see the second method its more efficient.

let arr = [20, 6, 7, 8, 50] 
 
function findNums(arr,sum){ 
  let temp = 0; 
  for(let i = 0;i<arr.length;i++){ 
    temp = arr[i]; 
    for(let j = i+1;j<arr.length;j++){ 
      temp += arr[j]; 
      if(temp === sum) return arr.slice(i,j+1); 
      if(temp > sum) break; 
    } 
  } 
  return []; 
} 
 
console.log(findNums(arr,21)) 
console.log(findNums(arr,13)) 
console.log(findNums(arr,50))

A better solution is what create a variable temp. Start adding elements to it one by one. When it becomes greater than given sum then remove the element from start of array.

let arr = [20, 6, 7, 8, 50] 
 
function findNums(arr,sum){ 
  let temp = arr[0]; 
  let low = 0; 
  for(let i = 1;i<arr.length;i++){ 
    temp += arr[i]; 
    if(temp === sum) return arr.slice(low,i+1); 
    while(temp > sum){ 
      temp -= arr[low] 
      low++; 
    } 
  } 
  return []; 
} 
 
console.log(findNums(arr,21)) 
console.log(findNums(arr,13)) 
console.log(findNums(arr,50))

For Negative Numbers

The problem with negative numbers is that we can't remove elements from start when the temp(current sum) becomes greater than given sum because we may have so negative numbers after in array which could make temp less than or equal to sum

For negative number you need to create an object to keep track of already calculated sums of subarrays.

let arr = [4,-2,-3,5,1,10] 
 
function findNums(arr,sum){ 
  let obj = {} 
  let temp = 0; 
  for(let i = 0;i<arr.length;i++){ 
    temp += arr[i]; 
    if(temp === sum) return arr.slice(0,i+1); 
    if(obj[temp - sum] != undefined){ 
      if(obj[temp-sum]+1 !== i){ 
        return arr.slice(obj[String(temp - sum)]+1,i+1); 
      } 
    } 
    obj[temp] = i; 
  } 
  return []; 
} 
 
 
console.log(findNums(arr,0)) 
console.log(findNums(arr,-1)) 
console.log(findNums(arr,13)) 
console.log(findNums(arr,1))

Answer 2

One possibility, depending upon how you want to use it, is to do as your attempt seems to try, and create a hashmap of partial sums, returning a function that will lookup in that hashmap for your value. Here, I do that, making the function curried so that you don't have to go to all the work of creating a hashmap for one set of numbers on every call.

The initial call is O(n^2), but subsequent calls are merely O(1). This style is useful if you want to search multiple values on the same set of numbers. If you only have one value to search, then a technique like the second one in Maheer Ali's answer would be more efficient.

const range = (lo, hi) => [...Array (hi - lo) ] 
  .map ( (_, i) => lo + i ) 
const sum = (nbrs) =>  
  nbrs .reduce ( (a, b) => a + b, 0 ) 
 
const findSequentialSum = (nbrs) => { 
  const subtotals = range (0, nbrs .length) 
    .flatMap ( 
      i => range (i + 2, nbrs .length + 1) 
        .map (j => nbrs .slice (i, j) ) 
    )  
    // .reduce((a, b) => a.concat(b), [[]]) 
    .reduce (  
      (a, sub, _, __, tot = sum(sub) ) => ({ 
        ...a,  
        [tot]: a [tot] || sub 
      }), 
      {} 
    ) 
  return (total) => subtotals [total] || [] 
} 
 
const nbrs = [20, 6, 7, 8, 50] 
 
const search = findSequentialSum (nbrs) 
 
console .log ( 
  search (21), //~> [6, 7, 8] 
  search (13), //~> [6, 7] 
  search (50), //~> [] 
)

The two helper functions should be straightforward: range(3, 10) //=> [3, 4, 5, 6, 7, 8, 9] and sum([2, 5, 10]) //=> 17

If flatMap isn't available in your environment, then you can replace

    .flatMap (
      i => range (i + 2, nbrs .length + 1)
        .map (j => nbrs .slice (i, j) )
    ) 

with

    .map (
      i => range (i + 2, nbrs .length + 1)
        .map (j => nbrs .slice (i, j) )
    ) 
    .reduce((a, b) => a.concat(b), [[]])

Also, the 2 in here

      i => range (i + 2, nbrs .length + 1)

requires sequences to be at least two entries long. If you wanted 50 to return [50] (which seems more logical to me), then you could just replace that 2 with a 1. Or you could replace it with something larger, if you wanted to find only sub-sequences of, say, length 5 or more.

Finally, if you wanted to return all subsequences that added to your total, it would be a simple modification, replacing:

        [tot]: a [tot] || sub

with

        [tot]: (a [tot] || []).concat([sub])
READ ALSO
Initializing multiple dbs with async await at the top level in node

Initializing multiple dbs with async await at the top level in node

I understand from a couple of similar questions that to use async await at the top level, it is necessary to wrap up anonymous functions

10
Connection refused between Node and MongoDB

Connection refused between Node and MongoDB

Getting this error when I try to connect my Node to my MongoDB

21
What claims do refresh token contain?

What claims do refresh token contain?

I am implementing JWT in one of my node appsI am wondering, if there is any definite format/ structure in which a refresh token should be generated?

27
How to get past errors using putParameter with aws-sdk for nodejs in Lambda?

How to get past errors using putParameter with aws-sdk for nodejs in Lambda?

I'm trying to set a parameter using putParameter in the AWS SDK for JavaScript in Nodejs

48