76. Find the Repeating and the Missing Number

An array contains n numbers that should be exactly the numbers 1 to n, each appearing once - except one number is missing and another appears twice (taking the missing one's place). Given the array, print 'repeating missing'.

Input: The first line contains an integer n. The second line contains n space-separated integers that should form 1..n with one value repeated and another missing. Output: Print the repeating number followed by the missing number, separated by a space.

2 <= n <= 10^5

The math-based approach hinges on knowing the exact formulas for the sum (n(n+1)/2) and sum of squares (n(n+1)(2n+1)/6) of the numbers 1 through n - worth memorizing these two formulas specifically for this class of problem.

An array should contain every number from 1 to n exactly once, but one number is missing and another number appears twice instead. Find both. Brute force: Check every number from 1 to n against the array directly by scanning for it each time - this costs O(n²), too slow for large n. Optimised: A single pass building a frequency count for every value directly reveals both answers immediately afterward (whichever value has count 2 is the repeat; whichever has count 0 is missing) - no repeated re-scanning needed. A pure-math alternative also exists: using the known formulas for the sum and sum-of-squares of 1 to n, you can set up two equations relating the actual array's sum/sum-of-squares to the expected ones, and solve for both unknowns algebraically without any extra array at all.

Make a single pass over the array, incrementing a count in a frequency array (or hash map) of size n indexed by value. Then make a second pass from 1 to n over the frequency table: the value with count 0 is the missing number, and the value with count 2 is the repeating number. This replaces repeated full scans with one scan to build counts and one scan to read them off, at the cost of extra memory proportional to n. Time: O(n) Space: O(n)

The expected sum of 1..n and expected sum of squares of 1..n can both be computed with closed-form formulas. Comparing these to the actual sum and actual sum-of-squares of the array gives two equations in the two unknowns (the missing value and the repeating value): the difference in sums equals repeating minus missing, and the difference in sum-of-squares equals (repeating - missing)(repeating + missing). Solving this small system of two linear equations algebraically recovers both numbers directly, with no extra array or hash map needed at all - just a couple of running totals. Time: O(n) Space: O(1)

For each candidate value x from 1 to n, scan the entire array and count how many times x occurs. A count of 0 means x is the missing number, and a count of 2 means x is the repeating number. This is a direct, obviously-correct check of the problem's definition, but it re-scans the whole array once per candidate, making it quadratic. Time: O(n^2) Space: O(1)

1. Count how many times each value from 1 to n actually appears in the array, using a frequency array or hash map. 2. The value with a count of exactly 2 is the repeating number. 3. The value with a count of exactly 0 is the missing number. 4. Print both.

Time: O(n) - one pass to count (or one pass to compute sums, in the math-based approach). Space: O(n) for the frequency-array approach, or O(1) for the pure-math sum-based approach.

n = 2 (smallest possible repeating/missing pair) and n = 10^5 (largest, to confirm the frequency or sum-of-squares approach avoids overflow); the repeated/missing value can fall at either end of the 1..n range (1 or n).

Be ready to present BOTH approaches (frequency counting, and the sum/sum-of-squares math trick) - interviewers often specifically ask for the O(1)-space math version as a harder follow-up once the straightforward counting solution is given.