1

Recently in an interview i was asked this question.

Given:

  1. a + or - b = 40 // You can choose any one operator + or -

  2. [list of any numbers in an array]

Explain how will you choose numbers for A and B from an given array to make the result 40 ?

My Answer:

Consider 1st element of array as A, now iterate through array from start to find possible values of B while this process fetch each element from array, sum up with A and compare it with 40.

But he was not happy.

Any other approaches ?

Wesley
  • 4,049
  • 6
  • 36
  • 59
Javed Solkar
  • 162
  • 10
  • First of all, your solution is partial, because you should repeat the process for every other element (not just the first one). Second, you should probably sort the array first, then your search would be faster than `O(n^2)`. – barak manos Apr 23 '15 at 06:08
  • Yes i gave partial solution just to explain the logic. I got your solution, Is there any other approaches without sorting. – Javed Solkar Apr 23 '15 at 06:11
  • 1
    See https://stackoverflow.com/q/4720271/6309: an hash table does not involve sorting. – VonC Jun 08 '17 at 20:30

1 Answers1

0

Sorting would definitely help you get the solution your interviewer has looked for:

  1. First, sort the array. Should take about O(nlogn).
  2. Now put 2 pointers, i and j. i starts at the beginning of the array, and j starts at the end.
  3. Compare the 2 values (that i and j point to) to 40. If the result is bigger than 40, j moves to the left. If the result is smaller than 40, i moves to the right. You will keep doing this until having two values with the sum of 40.
  4. If not found yet, do the same thing the other way around, for the subtraction of both values, to get 40.

The whole solution takes only O(nlogn) and is very elegant. Good Luck!

TS_
  • 289
  • 1
  • 5