How to solve “sumOfTwo” in CodeFights

The Problem:

You have two integer arrays, a and b, and an integer target value v. Determine whether there is a pair of numbers, where one number is taken from a and the other from b, that can be added together to get a sum of v. Return true if such a pair exists, otherwise return false.

Example

For a = [1, 2, 3], b = [10, 20, 30, 40], and v = 42, the output should be
sumOfTwo(a, b, v) = true.

Input/Output

  • [time limit] 4000ms (py)
  • [input] array.integer aAn array of integers.

    Constraints:
    1 ≤ a.length ≤ 105,
    -109 ≤ a[i] ≤ 109.

  • [input] array.integer bAn array of integers.

    Constraints:
    1 ≤ b.length ≤ 105,
    -109 ≤ b[i] ≤ 109.

  • [input] integer vConstraints:
    -109 ≤ v ≤ 109.
  • [output] booleantrue if there are two elements from a and b which add up to v, and false otherwise.

 The Solution:

Capture.PNG

The Explanation:

We can do this in len(a)*len(b) operations iterating over every single x,y combination but it would not run in short time. Therefore, we need a smarter solution. If we had two sorted arrays, then we would be sure that  whenever we go to the next element in the array, the sum would increase. Similarly, previous element would make the sum decrease.

Following that, if we start from the beginning of one array and end of the other. We can travel within the arrays and check the sum everytime.

For example, if we have [1,2,3,5] and [10,20,30,40] and we are looking for 33, we can do the following:

start from the beginning of first array and at the end of second

sum = 41

it is greater than our sum, so move the iterator in the second array to the left ro decrease the sum.

1+30 = 31

It is smaller, then move the iterator in the first array forward so that the sum increases

2+30 = 32

again…

3+33=33

If we were looking for 34, we would go to the next element, 35 would be bigger than the number we are looking for. That means we have no way of making the sum with these numbers because the smaller x’s are all depleted and bigger numbers will always result in bigger sums than we are looking for.

Feel free to shoot any questions.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s