Daily Coding Problem is a website which will send you a programming challenge to your inbox every day. I want to show beginners how to solve some of these problems using Scala, so this will be an ongoing series of my solutions. Feel free to pick them apart in the comments!

### Problem

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?

### Strategy

See my discussion of this problem (and my Java implementation) here!

### Code

Rather than using nested loops in an imperative style, as I did in my Java solution, I'd like to stick with a more functional approach for my Scala solution to this problem.

Scala provides a beautiful standard library, including `List`

s with methods like `combinations(n: Int)`

(which gives all combinations of `n`

elements in the `List`

), and `exists(p: List[T] => Boolean)`

, which returns `true`

if there exists at least one element in the list which satisfies the given predicate, `p`

. Combined with Scala's `implicit`

parameters and `Numeric`

type class under the hood (neither of which exist in Java), we can solve this problem in a single line of Scala code (not including the definitions of the list and `k`

themselves):

```
val ll: List[Int] = List(10, 15, 3, 7)
val k: Int = 17
ll.combinations(2).exists(_.sum == k) // returns true
```

That's it!

### Discussion

`ll.combinations(2)`

returns a `List[List[Int]]`

. That is, a `List`

which contains `List[Int]`

(lists of ints). The inner lists are all of the possible distinct pairs of elements of the list `ll`

.

Calling `exists(...)`

on a `List`

checks if any element of the list satisfies the function passed as the argument to `exists(...)`

. (Note that this requires Scala's support for higher-order functions.) The function I passed, `_.sum = k`

, checks each inner list (each element of `ll`

) using the underscore `_`

as a placeholder for each element in turn. Since each element is itself a `List[Int]`

, we can call the `sum`

function on that inner `List`

, and simply check if the sum is equal to `k`

.

Removing all this syntactic sugar, you might end up with something like:

```
// with syntactic sugar
ll.combinations(2).exists(_.sum == k)
// de-sugared
ll.combinations(2).exists(
(innerList: List[Int]) => innerList.sum == k
)
```

...but the Scala compiler knows that the type of `innerList`

must be `List[Int]`

, since `ll`

is of type `List[List[Int]]`

, so its elements are `List[Int]`

s. So we can drop the explicit type annotation:

```
ll.combinations(2).exists(
(innerList) => innerList.sum == k
)
```

...and when we declare an anonymous function with only a single argument, as above, we can drop the parentheses around that argument:

```
ll.combinations(2).exists(
innerList => innerList.sum == k
)
```

Finally, we can replace any number of anonymous function arguments with underscores `_`

, and the Scala compiler will replace them, one by one, in the function definition:

```
ll.combinations(2).exists(_.sum == k)
```

The end result of all of this syntactic sugar is a compact bit of code that is easy to read and error check. You can see why I like Scala so much, especially compared to the verbosity of my (not purposefully obfuscated) Java solution!

All the code for my Daily Coding Problems solutions is available at github.com/awwsmm/daily.

Suggestions? Let me know in the comments.

If you enjoyed this post, please consider supporting my work by buying me a coffee!

## Discussion (3)

Andrew, Hi!

This problem is often at interviews, I dare say, so be careful :)

Your final solution with

`combinations`

and`exists`

is definitelynot one pass. It is`N*N`

but wrapped in thin layer of deceiving FP style :)Try filling list with 1 million random elements and you'll see what I mean...

Thanks for pointing that out! How would you solve this in a single pass?

Putting elements to HashSet and looking up for K-element... It will make O(N) solution.