Daily Coding Problem: Problem #1

Daily Coding Problem: Problem #1
0

#1

If you are wondering what’s this thing? Then before continuing, please read this.

Problem #1

This problem was recently asked by Google.

Given a list of numbers and a number k , return whether any two numbers from the list add up to k.
For example, given [10, 15, 3, 7] and k of 17 , return true since 10 + 7 is 17 .

Bonus: Can you do this in one pass?


Solve. Discuss. Repeat. Happy Coding!


#2

Here’s what I coded:

#include <iostream>
using namespace std;

int main()
{
  int list[4];
  int k;
  cout << "Enter 4 numbers: \n";
  for (int i = 0; i < 4; ++i)
  {
    cin >> list[i];
  }
  cout << "Enter 'k': ";
  cin >> k;
  for (int i = 0; i < 4; ++i)
  {
    for (int j = i + 1; j < 4; ++j)
    {
      if (list[i] + list[j] == k)
      {
        cout << "\nTRUE!\n\n";
        return 1;
      }
    }
  }
  cout << "\nFALSE!";
  return 0;
}

I know this can be further optimized. I am working on improving this. I would love to hear from you all.


#3

Possible JS solution:

function permSum(arr, target) {
  // memoize to prevent duplicate calculations:
  const hmap = {};
  
  // find permutations of the array values:
  for (const a of arr) {
    for (const b of arr) {
      if (a != b) {
        // cache the sum:
        const sum = a + b;
        // if the sum is in the hash map, already been checked, so ignore:
        if (!(sum in hmap)) {
          // return immediately if the target is found:
          if (sum == target) return true;
          // else memoize the sum:
          hmap[sum] = null;
        }
      }
    }
  }
  // array has been fully iterated, no target found:
  return false;
}

#4
function iPlusJEqualsK(arr, k) {
  let i = 0;
  while (i < arr.length) {
    for (let j = 0; j < arr.length; j++) {
      if (j === i) {continue;} // don't add num to itself
      if (arr[i] + arr[j] === k) {return true;}
    }
    i++;
  }
  return false;
}


#5

JS

i think this is valid

hasAnAddingPair = (numbers, k) => { 
  for(let number in numbers){
    for(let i = number; i < numbers.length-1; i++) {
      //console.log(`${numbers[number]} + ${numbers[Number(i)+1]} = `, numbers[number] + numbers[Number(i)+1])
      if(numbers[number] + numbers[Number(i)+1] === k){
        return true
      }
    }
  }
  return false
}

#6

Here is my attempt at a one pass solution. Seems to be working by my tests. Feel free to break and let me know. :grin:

 <script>
    const arr = [10, 15, 3, 7];
    const target = 17; 
    let diff = 0;
   

    //Given a list of numbers and a number n, return whether any two numbers from the list add up to n.
    const sumOfTwo = (arr, target) => {
      let result = "false";
      let tempArr = [];
      
      for (let i = 0; i < arr.length; i++) { 
        tempArr = arr.slice(0); //Set temp array to arr's values.
        tempArr.splice(i,1); //Remove the current element. Easy way to check other values with find().
       
        //Find the difference between the target number and current value.
        diff = target - arr[i];

        if (tempArr.find(checkForValue) !== undefined){
          result = "[" + arr[i] + ", " + diff + "] true";
          break;
        }
      }

      return result;
    }

    //Look for an array value that matches the diff.
    const checkForValue = (numVal) => {
      return numVal == diff;
    }

    console.log(sumOfTwo(arr, target));
  
  </script>

#7

This is a “one pass” solution in the sense that it only iterates over the whole original array once. I loop through the growing array of complementary values as we go, and that array grows in length over time but starts small, so its not quite as sloppy as it could be. I push onto diffs after checking so I don’t return true when I get a number equal to exactly half of k. It feels like this could miss something, since diffs starts incomplete, but I don’t think it can, because if your complement wasn’t behind you, it’s ahead of you.

function findComplements(array, k) {
	let diffs = [];
	for (let i = 0; i < array.length; i++) {
		for (let j = 0; j < diffs.length; j++) {
			if (array[i] == diffs[j]) {
				return true;
			}
		}
		diffs.push(k - array[i]);
	}
	return false;
}

#8

@DanCouper 's solution is pretty interesting, but it looks like this doesn’t allow duplicates to return true. [8, 1, 5, 8, 10] for k = 16 returns false.

I think you’re trying to prevent a and b in arr from being at the same index, but it also precludes the same number at different indices.

I would really like to understand the intention behind the hmap object. Would you (or someone) mind explaining how it works?


#9

I probably should ask for some clarification.

  1. Do numbers repeat in the Array?
  2. Is there a need to know the pair of number that sums up to k, or if there are multiple pair, all the pairs in a future implementation?

#10

That is very true, I was still in the mindset of another problem where I needed unique permutations, so the a != b check should be removed. The hashmap isn’t necessary in the form I have it, that was me still thinking about the other problem again; this should work, it’s not very efficient though, I should be able to half the permutations by memoizing but anyway

function permSum(arr, target) {
  for (const a of arr) {
    for (const b of arr) {
        if (a + b == target) return true;
    }
  }
  return false;
}

Edit: hmap was me putting memoization in without really implemeting it usefully. If I’d actually had my brain working, it would have been there to prevent recalculating values that have already been calculated…but I didn’t, hence why it’s currently pointless.


#11

Well now I have a new thing to look up. Memoizing. Very cool, thanks.


#12

I hate to do it but you did ask: this returns true for items with a difference equal to the target, and for a single item that is exactly half the target.


#13

No that’s fine, I should have tested more intensively and I learned from digging through this. So, my logic was flawed and I went back to the drawing board and updated my solution. I tested against the points you made as well as some other random positive and negative values and everything seems to work now as expected.


#14

Glad to hear it. Would love to see!


#15

Here’s what I got. I think it’s one path.

function addUp(nums, k) {
	for (let i = 0, obj = {}; i < nums.length; i++) {
	
		let num = nums[i];
		let dif = k - num;
		
		// if num is in obj already, add 1 to it. otherwise, set it equal to 1.
		obj[num] = (num in obj) ? obj[num]+=1 : 1;
		
		// if current num is equal to the difference and the count is not 2, move on.
		if (num == dif && obj[num] != 2) {
			continue;
		}
		
		// otherwise, the difference was found.
		if (dif in obj) { 
			return true;
		}
	}
	return false;
};
addUp([2], 4);  //false
addUp([2, 2], 4);  //true
addUp([15, 2, 3, 2, 9], 4);  //true