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
}
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))
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))
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])
Drop down menu does not work with Bootstrap version 3.4.1 and Jquery >= 3.0.0
What is the proper Query and PHP to print an archive of the database based on Year, Month?
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
Getting this error when I try to connect my Node to my MongoDB
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?
I'm trying to set a parameter using putParameter in the AWS SDK for JavaScript in Nodejs