  Apple

## Interview Question

Senior Software Engineer Interview

-

# In a stream of integers from 1 to n, only one number will be repeated. How can you tell what that number is?

21

You know n. S = n*(n+1)/2 is the sum of 1st n numbers. P = sum of the n+1 numbers you are provided with. Finding P given an array of n+1 integers can be done in O(n). P - S is the repeated integer.

Anonymous on

1

If you're writing it in ruby def find_repeat(numbers) numbers.length.times{|n| return numbers[n] if numbers[n] != n } end

Anonymous on

0

Mat, try 1,2,2,3: 1+2+2+3= 8 1^2^2^3= 2 (8-2)/2=3?2

OZone on

0

Add to HashSet. It will return true if it exists.

Anonymous on

0

Add each integer to the map if it doesn’t already exist as key if it’s exists then it is a repeated number.

Anonymous on

1

lmao, ok everyone getting a little craycray, why not just simply this.... int prev << stream; while (stream) { int curr << stream; if curr == prev return else prev = curr; }

notorious on

0

(sum_of_numbers - (n*(n-1)/2))

Anonymous on

0

A hash table would resolve the question with O(n)

Jobhunter on

3

int sum = 0; int xorSum = 0; for(int i =0 ; i < n; i++) { sum += input[i]; xorSum ^= input[i] } return (sum - xorSum)/2;

Mat on

1

This felt like a brain teaser question to me, and since I hadn't heard it before it took me a little while to come up with a solution that involved using a factorial function.

Anonymous on

2

Heres an explanation, http://www.techinterview.org/post/526329049/sum-it-up

Anonymous on 