Daily Coding Problem #1

For quite some time I found my time procastinating after getting home from work. Untill a few days ago I stumbled upon the Daily Coding Problem (DCP) and decided to give it a shot.
The code is in C#.

How it works?

The folks at DCP send you a problem that was asked at a top company everyday for you to solve. The premium membership also offers the opportunity to verify your solution.

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?

My solution

using System;
using System.Collections.Generic;
using System.Linq;

namespace Problem01
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var numbers = Console.ReadLine()
                .Split(' ')
                .Select(int.Parse)
                .ToList();

            var k = int.Parse(Console.ReadLine());

            var result = TwoNumbersEqual(numbers, k);
            Console.WriteLine(result);
        }

        public static bool TwoNumbersEqual(List<int> numbers, int k)
        {
            var set = new HashSet<int>();

            foreach (var number in numbers)
            {
                var remaining = k - number;

                if (set.Contains(remaining))
                {
                    return true;
                }

                set.Add(number);
            }

            return false;
        }
    }
}

Explanation

The naive solution would be to do two nested for loops and check if any of the combinations gives the k we desire.
But because I wanted the bonus tag and after some tought, I realized that you could foreach the input array and for each item check find the difference between it and k. After you find the difference, you can check if you have already seen this number before and the HashSet data structure allows for constant lookups (because it is a hash table).

I will try to do the daily problem everyday, but sometimes life gets in the way :)
Solutions are posted in my github account

cwetanow / DailyCodingProblem

DailyCodingProblem

This repository contains solutions of the Daily Coding Problem tasks

View on GitHub

.

Feel free to leave a like and let me know in the comments if I should continue to post my solutions.

If you also have any better solution in mind, by all means share it, so we can learn from each other.

Comments

[websplee]

using System;

namespace PlayGround
{
class DailyProblems
{
int[] numArray;
int arraySize = 0;
int sumValue = 0;

    public void ElementsSum()
    {
        Console.Write("Enter sum value: ");
        sumValue = Convert.ToInt32(Console.ReadLine());
        Console.Write("Enter the size of the array :");
        arraySize = Convert.ToInt32(Console.ReadLine());
        // Initialize array
        numArray = new int[arraySize];

        // Get input for the array elements
        for (int i = 0; i < arraySize; i++)
        {
            Console.Write("Element " + (i + 1) + ": ");
            numArray[i] = Convert.ToInt32(Console.ReadLine());
        }

        Console.WriteLine("Moment of truth...: " + MyEvaluate());
        Console.ReadLine();
    }

    private bool MyEvaluate()
    {
        bool flag = false;
        int difValue = 0;

        for (int i = 0; i < arraySize; i++)
        {
            if (sumValue > numArray[i])
            {
                difValue = sumValue - numArray[i];
                for (int k = i+1; k < arraySize; k++)
                {
                    if (difValue == numArray[k])
                        return true;
                }
            }
        }

        return flag;
    }
}

}

[Subramanian 😎]

github.com/subsr97/daily-coding-pr...
This is my git repo which contains solutions in Python! :)

[Nishant Kumar]

// Input [10, 5, 7, 3] k=17

function findSumPair(numbs, sum) {
  if (!(numbs instanceof Array)) throw new Error("Invalid Numbers Input");

  const pairSet = new Set();
  let pair = undefined;

  numbs.some(item => {
    const temp = sum - item;
    if (temp > 0 && pairSet.has(temp)) {
      pair = [temp, item];
      return Boolean(pair);
    } else {
      pairSet.add(item);
    }
  });

  return pair;
}

console.log(findSumPair([10, 5, 7, 3], 17));

[KrishnanandP]

This is a pythonic code:-

Only taking 3 factors for this problem

def num(k,a,b,c):
assert a + b or b + c or c + a == k
if a + b == k:
print("True")
elif b + c == k:
print("True")
elif c + a == k:
print("True")
else:
print("False")

[Matt]

Well as a student here is a less elegant attempt. But I think it gets the job done

[Tristan 'Natrist' Cormier]

Here is my solution in C++

[Simone Natalini]

Don't know if it suits the problem given the fact that it'll output true/false on each item in the HashSet but here's my take on the problem

static void SumExists(HashSet<int> values, int k)
{        
   foreach (var item in values)
   {
       Console.WriteLine(values.Count(x => x + item == k) > 0);
   }
}

I know Count() maybe adds unneeded complexity and it may not be a one pass.
I'm looking for feedback here.

[Jay]

Rust solution:

use std::collections::HashSet;

fn two_add_upto(list: &[i32], k: i32) -> bool {
    let mut set = HashSet::with_capacity(list.len());

    for i in list.iter() {
        let diff = k - i;
        if set.contains(&diff) {
            return true;
        }
        set.insert(i);
    }
    false
}

Made a sized Set to overcome the reallocation and copying of data. This increases the Size requirement to O(N).

[Zulhaj Choudhury]

Hi Ivan,

I'm trying to understand this better.
How come you didn't do numbers.contains() instead of set.contains()? Does using the original list of numbers violate one pass?

[Ivan]

Because numbers.contains() is a list and to see if it contains the element would loop through the whole list (basically O(n). That makes the solution to have two nested loops and going full O(n^2)

[Pavitra Golchha]

Probably the shortest

const twoNumbersEqual = (a, k) => !!a.filter(x => a.includes(k-x)).length

twoNumbersEqual([10, 15, 3, 7], 17) // == true
twoNumbersEqual([10, 13, 4, 7], 17) // == true
twoNumbersEqual([10, 15, 3, 9], 17) // == false

[Casey Webb]

slight improvement with a short circuit (find vs filter):

const twoNumbersEqual = (a, k) => !!a.find(x => a.includes(k-x))

[Casey Webb]

I just realized both of these solutions fail in the case of twoNumbersEqual([5], 10). This can be fixed by passing the index to includes, as such...

(a, k) => !!a.find((x, i) => a.includes(k-x, i+1))

This should also theoretically be more performant.