Coding

Find the repeating and missing number

Asked at

Google

J.P. Morgan

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an integer array **nums **of size n containing values from [1, n] and **each **value appears **exactly **once in the array, except for A, which appears **twice **and B which is missing.

Return the values A and B, as an array of size 2, where A appears in the 0-th index and **B **in the 1st index.

**Note: **You are not allowed to modify the original array.

Input: nums = [3, 5, 4, 1, 1] Output: [1, 2] Explanation: 1 appears two times in the array and 2 is missing from nums

Input: nums = [1, 2, 3, 6, 7, 5, 7] Output: [7, 4] Explanation: 7 appears two times in the array and 4 is missing from nums.

Input: nums = [6, 5, 7, 1, 8, 6, 4, 3, 2]

n == nums.length
1 <= n <= 105
n - 2 elements in nums appear exactly once and are valued between [1, n].
1 element in nums appears twice, and is valued between [1, n].

cpp

class Solution {
public:
    vector<int> findMissingRepeatingNumbers(vector<int> nums) {

    }
};

java

class Solution {
    public int[] findMissingRepeatingNumbers(int[] nums) {

    }
}

python

class Solution:
    def findMissingRepeatingNumbers(self, nums):

javascript

class Solution {
    findMissingRepeatingNumbers(nums) {

    }
}

csharp

public class Solution {
    public List<int> FindMissingRepeatingNumbers(List<int> nums) {

    }
}

func findMissingRepeatingNumbers(nums []int) []int {

}

Stuck? Show a way to structure it+

01Compute expected and observed sums and squared sums, or use XOR partitioning.
02Derive duplicate-minus-missing from the sum difference.
03Solve for both values and preserve output order.
04Use wide numeric types for arithmetic.

Reference answer

Let d be repeated and m missing. Compute S = sum(nums)-n(n+1)/2 = d-m and Q = sumSquares(nums)-n(n+1)(2n+1)/6 = d²-m²; then d+m = Q/S, so solve both values. This is O(n) time and O(1) space, but requires wide integers. XOR is another O(1)-space approach: XOR all array and expected values, split by a distinguishing bit, then determine which candidate is present twice. Sorting or frequency arrays are simpler alternatives with different tradeoffs. In an interview, make the invariant explicit before writing code, trace a boundary example that breaks a tempting shortcut, state what each stored value represents, and explain why every update preserves correctness. This verification step also surfaces empty-input, duplicate-value, and numeric-limit cases.

Then expect these follow-ups

Explain the XOR partition solution.
Tests: bit manipulation
What changes with multiple duplicates and missing values?
Tests: problem limits

Hiring now

Google has 52 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Small Business Field Sales Representative
Denver, Colorado
Senior Technical Program Manager, Special Projects
Denver, Colorado; Lakewood, Colorado, United States
OSP Engineering Lead, Technical Operations
Denver, Colorado

Or practice this question first

Next question