Find out if any two elements in a list sum to a specific value in R

Question

This is a classic interview problem. Given a list numbers and a specific value k, find out if any two elements in numbers are equal to k when summed. How would one solve this in r in a single pass algorithm, rather than an exhaustive search?

In practical terms: write the most optimal function in r that receives a list numbers and a specific value k, returning TRUE if there are two elements in numbers that when summed equal to k. If there aren't, return FALSE.

Answer 1

This problem could be framed as: is there any a and b in numbers, such that: a + b = k? Considering you already know k, and assuming there actually are two numbers that when summed are equal to k, one could assume that:

a = k - b or b = k - a.

So by doing k - numbers we would be essentially solving the right sides of both the equations above. For example:

numbers <- c(10, 12, 6, 3) and k <- 9. k - numbers would return c(-1, -3, 3, 6). See how 3 and 6 showed up?

To do all this in R, one could define a function

sum_finder <- function(numbers, k) {
    diff_sequence <- k - numbers
    condition <- any(numbers %in% diff_sequence)
    return(condition)
}

Or simply:

sum_finder <- function(numbers, k) {
    return(any(numbers %in% (k - numbers)))
}

EDIT: for benchmarking purposes, I'll be posting here the solutions posted so far and the performance results by using microbenchmark::microbenchmark().

# as posted by @eduardokapp
function1 <- function(numbers, k) {
    any(numbers %in% (k - numbers))
}

# as posted by @AnilGoyal
function2 <- function(numbers, k) {
    any(apply(outer(numbers, numbers, `+`), 1, function(x){x == k}))
}

# Performance Comparison
numbers <- sample(500, 500)
k <- sample(500, 1)
microbenchmark::microbenchmark(
   function1(numbers, k),
   function2(numbers, k)
)

Performance Comparison

Unit: MICROSECONDS

expr	min	lq	mean	median	uq	max	neval
function1(numbers, k)	13.651	21.277	39.58225	27.4485	40.1905	277.256	100
function2(numbers, k)	5061.088	5805.186	10971.04516	7571.6030	13316.1325	47782.874	100