PPractick

The problem

A stadium sells N tickets numbered 1 to N. At the end of the day the scanner log has N entries, but one ticket number was scanned twice (someone shared a ticket) and consequently one number never appears. Security wants both numbers. Counting with a hash map or a boolean array is O(n) space. The O(1)-space answer uses maths: the log's sum and sum of squares differ from those of 1..N by amounts that depend only on the repeating number x and the missing number y, which gives two equations in two unknowns.

Example: [3, 1, 3] → repeating 3, missing 2.

Function signature

pair<int, int> findRepeatingAndMissing(const vector<int>& a);  // {repeating, missing}; a has N values from 1..N

Test cases

Input a	Output	Explanation
[3, 1, 3]	{3, 2}
[4, 3, 6, 2, 1, 1]	{1, 5}
[1, 1]	{1, 2}
[2, 2]	{2, 1}
[1, 2, 2, 4]	{2, 3}

(Confirm: exactly one value in 1..N appears twice and exactly one is missing; O(1) extra space is the goal.)

How interviewers phrase it

• "Find the missing and repeating number" (GeeksforGeeks, InterviewBit "Repeat and Missing Number Array").
• "Set mismatch" (LeetCode 645) is the same problem.

Clarifying questions to ask

1. Exactly one repeat and one missing value?
2. Can I modify the array? (Some solutions mark visited values by negating.)
3. How large is N? (Sums of squares need 64-bit.)

Follow-ups to expect

1. "Derive the equations."
2. "Can it overflow?"
3. "What's the XOR approach?"
4. "What if you may modify the array?"
5. "Complexity?"

Related questions

• Longest Consecutive Sequence in an Array Medium
• Set Matrix Zeroes Medium
• Find missing number Easy
• Kth Missing Positive Number Easy
• Find the number that appears once, and other numbers twice Medium
• Longest subarray with given sum K (positives) Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in