SubArraySum

Solving problem with javascript really fun. Lets build the basic build blocks.

Problem: In an array of integers find the number of combinations of subarray for an expected target. Take a use case in real life, you have $50 in hand. You can pick items next to each other in an aisle. Find how many possibilities. Price of each item given as follows.

[10, 12,  38,  20, 10, 5, 15]

How do we pick in real life? We can pick items [12, 38] or [20, 10, 5, 15] which are continues.  It is easy for us when such a small data provided. Imaging 1000 continues array like below: 

[8,  43, 24, 98, 39, 48, 96, 16, 60, 61, 74, 52, 82, 45, 37, 4, 69, 26, 40, 5, 5, 4, 51, 78, 47, 94, 89, 35, 33, 28, 2, 97, 69, 74, 57, 45, 90, 64, 36, 23, 88, 96, 63, 100, 86, 33, 4, 29, 18, 2, 21, 11, 6, 100, 82, 33, 10, 92, 23, 47, 95, 56, 37, 98, 3, 64, 40, 22, 97, 92, 79, 40, 12, 70, 43, 4, 93, 71, 96, 57, 22, 18, 93, 67, 41, 56, 89, 98, 6, 91, 43, 89, 87, 2, 65, 10, 44, 31, 31, 80, 69, 83, 66, 26, 92, 30, 24, 78, 87, 47, 24, 30, 55, 27, 75, 13, 66, 55, 63, 13, 48, 32, 20, 39, 3, 41, 9, 6, 4, 57, 12, 6, 33, 83, 16, 80, 43, 81, 83, 81, 59, 21, 7, 73, 73, 18, 100, 19, 14, 29, 8, 66, 58, 38, 63, 29, 95, 16, 50, 89, 48, 61, 52, 40, 61, 70, 81, 37, 18, 33, 47, 51, 77, 24, 99, 49, 22, 26, 50, 47, 77, 62, 20, 17, 53, 79, 70, 17, 65, 57, 52, 19, 80, 83, 25, 72, 20, 62, 52, 50, 7, 71, 63, 68, 96, 99, 44, 21, 100, 25, 12, 29, 10, 49, 73, 87, 87, 98, 40, 98, 71, 17, 79, 64, 78, 61, 37, 64, 99, 46, 70, 78, 63, 86, 73, 69, 92, 28, 60, 93, 37, 14, 70, 91, 100, 80, 9, 36, 68, 14, 34, 81, 23, 29, 71, 70, 70, 25, 8, 30, 13, 18, 12, 8, 49, 97, 51, 80, 83, 34, 29, 72, 8, 49, 50, 5, 26, 61, 15, 61, 62, 93, 3, 1, 83, 69, 10, 2, 23, 95, 55, 41, 10, 68, 4, 12, 30, 48, 36, 1, 5, 44, 92, 46, 84, 49, 8, 62, 72, 69, 49, 21, 25, 14, 52, 42, 18, 83, 18, 38, 42, 95, 83, 91, 50, 12, 14, 36, 97, 40, 13, 19, 18, 62, 30, 74, 58, 6, 84, 83, 59, 17, 37, 99, 36, 56, 62, 22, 71, 62, 5, 92, 45, 47, 69, 58, 54, 12, 76, 27, 79, 41, 24, 4, 63, 31, 63, 65, 29, 6, 72, 56, 66, 83, 10, 93, 68, 85, 74, 18, 90, 70, 11, 91, 7, 68, 59, 81, 54, 49, 10, 91, 8, 68, 26, 36, 82, 69, 54, 62, 36, 52, 67, 51, 94, 60, 81, 56, 78, 1, 47, 14, 28, 98, 38, 74, 3, 31, 89, 67, 54, 30, 72, 87, 5, 4, 75, 23, 60, 58, 13, 71, 9, 6, 76, 34, 15, 34, 11, 44, 13, 24, 63, 91, 72, 80, 72, 2, 6, 15, 76, 13, 70, 60, 5, 64, 10, 45, 95, 100, 70, 69, 45, 2, 39, 27, 34, 50, 19, 37, 43, 34, 74, 87, 64, 65, 58, 88, 68, 45, 23, 78, 96, 14, 37, 75, 51, 49, 11, 10, 61, 91, 36, 9, 5, 60, 18, 67, 77, 81, 43, 11, 88, 18, 49, 52, 3, 90, 49, 35, 48, 10, 82, 75, 37, 30, 69, 28, 28, 55, 95, 7, 97, 17, 77, 95, 19, 43, 50, 42, 21, 36, 93, 19, 61, 93, 55, 89, 99, 22, 15, 41, 75, 79, 11, 6, 24, 77, 54, 91, 82, 28, 71, 14, 10, 80, 76, 36, 26, 56, 91, 21, 7, 15, 40, 80, 13, 69, 24, 40, 69, 58, 39, 44, 45, 9, 82, 36, 1, 52, 24, 71, 62, 63, 76, 42, 65, 14, 49, 81, 100, 84, 83, 11, 64, 12, 32, 33, 43, 85, 50, 66, 32, 99, 5, 64, 26, 5, 83, 75, 12, 2, 66, 54, 98, 61, 53, 45, 58, 51, 90, 30, 47, 62, 86, 44, 27, 25, 59, 9, 7, 40, 38, 90, 56, 68, 67, 37, 1, 4, 6, 13, 84, 32, 73, 9, 53, 50, 6, 12, 37, 75, 29, 44, 58, 61, 3, 31, 11, 42, 2, 27, 47, 70, 13, 9, 91, 84, 1, 64, 84, 44, 1, 65, 54, 92, 74, 60, 62, 17, 57, 87, 51, 15, 89, 28, 2, 5, 60, 21, 85, 72, 70, 55, 100, 92, 92, 8, 29, 39, 29, 10, 69, 67, 27, 8, 20, 95, 75, 7, 59, 79, 74, 76, 94, 63, 74, 94, 93, 6, 2, 32, 78, 64, 46, 77, 5, 18, 9, 1, 33, 51, 86, 19, 98, 96, 51, 32, 34, 93, 41, 54, 29, 6, 89, 85, 23, 42, 21, 87, 63, 28, 95, 50, 8, 94, 41, 85, 75, 52, 11, 31, 97, 64, 8, 56, 41, 97, 42, 45, 50, 11, 22, 70, 95, 71, 9, 35, 93, 68, 74, 54, 66, 58, 99, 80, 58, 17, 27, 59, 39, 48, 53, 48, 67, 55, 74, 14, 49, 11, 55, 52, 1, 16, 58, 33, 18, 6, 12, 96, 76, 65, 52, 77, 22, 70, 39, 21, 34, 65, 25, 42, 68, 46, 77, 98, 36, 97, 69, 80, 10, 16, 59, 50, 87, 63, 25, 83, 99, 76, 37, 71, 17, 47, 77, 60, 74, 38, 93, 56, 18, 68, 16, 46, 62, 97, 61, 69, 91, 83, 29, 83, 18, 33, 86, 61, 16, 45, 73, 49, 6, 97, 31, 88, 62, 31, 41, 5, 37, 75, 28, 74, 81, 29, 89, 55, 64, 61, 71, 79, 97, 38, 11, 2, 43, 69, 38, 52, 6, 18, 19, 64, 42, 85, 24, 47, 60, 3, 71, 42, 81, 91, 32, 97, 71, 9, 53, 25, 99, 18, 69, 20, 46, 96, 41, 37, 38, 65, 91, 31, 5, 8, 72, 36, 20, 65, 25, 11, 32, 85, 29, 17, 63, 21, 92, 4, 83, 46, 92, 20, 91, 31, 14, 59, 92, 1, 35, 45, 50, 95, 23, 92, 54, 90, 46, 90, 88, 11, 52, 36, 9, 80, 27, 9, 63, 18, 5, 49, 48, 14, 39, 17, 16, 20, 34, 37, 16, 79, 73, 51, 61, 23, 50, 95, 12, 66, 4, 14, 98, 60]

Not an easy job. Let us instruct computer to do that this way.

We: Hey Computer take continues items and find continues items sums up $50.

Computer: what is a continues item?

We: Items appearing next to one another.

Computer: ok

We: sum it and find the total

Computer: sure, it is $49344

We: ???? Are you an idiot?

Computer: 😔

Computer struggles to understand our instructions. Let us simplify using one of the computer known language - javascript.

The code above uses lot of memories to store intermediate values such as sum and i. It is not a problem with advanced computers we are using now a days.  We instruct computer how to add an array of numbers. But even now, if we pass entire data we have it is going to give same old result. Not good. 

How to get sub array in javascript? there is method called slice will help.

First one slicing from position 1. Second one slicing 4 items from the starting. so slice method takes starting position and number of items.

Using this we can give instructions how to get subarrays.

when we run, we get this

passing these values to our sum function, we can find whether we get our expected target.

When we run we get below result

Now it is easy for us to calculate number of items matches our target.

Input: [10, 12,  38,  20, 10, 5, 15]

target: 50

passing it to our function is generating following result.

Does it help? No. It is not giving the result what we expect. But sum up all numbers and discard one each item to generate new sum. It is not the one we are expecting. But we learnt, few basic building blocks how to find. Try and share your code in comments.