Home

# Daily Coding Problem #1 - Two Sum

February 17, 2019

From today I’ll try to solve a programming problem every single day using Golang and push it up to https://github.com/khoi/daily-coding-problem-in-go/ These programing problems are tailored, curated by Daily Coding Problem. I highly recommend that you subscribe to them to exercise your brain everyday.

The first problem I’m solving today is `Two Sum`, which should be a trivial one.

## Problem

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?

## Solution

This can be solved in just 1 pass, by storing all the number that we’ve passed through in a `map[int]struct{}`. And for each element, we check whether the `map[k - currentNumber]` exist. If it exists, then we find a match!

1_two_sum.go

``````package daily_coding_problem_in_go

func TwoSum(nums []int, k int) bool {
m := make(map[int]struct{})

for _, e := range nums {
if _, ok := m[k-e]; ok {
return true
}
m[e] = struct{}{}
}

return false
}
``````

1_two_sum_test.go

``````package daily_coding_problem_in_go

import "testing"

var tests = []struct {
arr      []int
k        int
expected bool
}{
{[]int{10, 15, 3, 7}, 17, true},
{[]int{10, 15, 3, 7}, 10, true},
{[]int{10, 15, 3, 7}, 3, false},
{[]int{10, 15, 3, 7}, 26, false},
}

func TestTwoSum(t *testing.T) {
for _, tc := range tests {
if actual := TwoSum(tc.arr, tc.k); actual != tc.expected {
t.Errorf("arr = %v, k = %v, got %v, want %v", tc.arr, tc.k, actual, tc.expected)
}
}
}
``````

Time Complexity: O(n)