Test-Driven Code

Two missing numbers

by Tom

Signature

def find_two_missing(numbers: list[int], n: int) -> set[int]:

Test Code

import random assert find_two_missing([], 2) == {0, 1} assert find_two_missing([0], 3) == {1, 2} assert find_two_missing([1], 3) == {0, 2} assert find_two_missing([2], 3) == {0, 1} assert find_two_missing([1, 2], 4) == {0, 3} assert find_two_missing([4, 2, 0], 5) == {1, 3} assert find_two_missing([0, 1, 2, 5], 6) == {3, 4} assert find_two_missing([5, 2, 1, 0], 6) == {3, 4} def test(): for n in range(2, 101): numbers = list(range(n)) random.shuffle(numbers) real_missing_numbers = {numbers.pop() for _ in range(2)} random.shuffle(numbers) missing_numbers = find_two_missing(numbers, n) assert real_missing_numbers == missing_numbers, f"Test failed for {n=}. Expected {real_missing_numbers}, got {missing_numbers} for {numbers=}" if __name__ == "__main__": test()

Description

Given an array of length n - 2 containing distinct numbers from 0 to n - 1 with two missing numbers, find the missing two numbers.

Submit a Solution

Fastest Solutions

Solution by Tom (0.2 seconds)

def find_two_missing(numbers: list[int], n: int) -> set[int]: seen = [False] * n for number in numbers: seen[number] = True unseen_numbers = {i for i in range(n) if not seen[i]} return unseen_numbers

Solution by Anonymous User #43 (0.2 seconds)

def find_two_missing(numbers: list[int], n: int) -> set[int]: total_sum = n * (n - 1) // 2 arr_sum = sum(numbers) missing_sum = total_sum - arr_sum total_sq_sum = (n - 1) * n * (2 * (n - 1) + 1) // 6 arr_sq_sum = sum(x * x for x in numbers) missing_sq_sum = total_sq_sum - arr_sq_sum # Let the two missing numbers be a and b # a + b = missing_sum # a^2 + b^2 = missing_sq_sum # (a + b)^2 = a^2 + b^2 + 2ab # ab = (missing_sum^2 - missing_sq_sum) / 2 ab = (missing_sum * missing_sum - missing_sq_sum) // 2 # Solve for a and b using quadratic equation derived from: # x^2 - (a + b)x + ab = 0 # x^2 - missing_sum * x + ab = 0 # Discriminant = missing_sum^2 - 4 * ab discriminant = missing_sum * missing_sum - 4 * ab a = (missing_sum + discriminant ** 0.5) // 2 b = missing_sum - a return {int(a), int(b)}

Solution by Tom (0.2 seconds)

from math import isqrt def find_two_missing(numbers: list[int], n: int) -> set[int]: # This solution only requires O(1) additional memory. # sum numbers and squares of numbers x1 = sum(numbers) x2 = sum(x**2 for x in numbers) # expected sums for full list of numbers y1 = n * (n - 1) // 2 # https://www.wolframalpha.com/input?i=sum+i+with+i+from+0+to+n+-+1 y2 = n * (n - 1) * (2 * n - 1) // 6 # https://www.wolframalpha.com/input?i=sum+i*i+with+i+from+0+to+n+-+1 # solve the following two equations for solutions s1 and s2 # x1 + s1 + s2 = y1 # x2 + s1**2 + s2**2 = y2 d = y1 - x1 s = isqrt(2 * (y2 - x2) - d**2) s1 = (d - s) // 2 s2 = (d + s) // 2 return {s1, s2}

Solution by Tom (0.2 seconds)

def find_two_missing(numbers: list[int], n: int) -> set[int]: return set(range(n)) - set(numbers)

Solution by Anonymous User #42 (0.2 seconds)

def find_two_missing(numbers: list[int], n: int) -> set[int]: # Sum of full range from 0..n-1 full_sum = (n * (n - 1)) // 2 given_sum = sum(numbers) missing_sum = full_sum - given_sum # a + b # Sum of squares of full range full_sq = (n - 1) * n * (2 * n - 1) // 6 given_sq = sum(x * x for x in numbers) missing_sq = full_sq - given_sq # a² + b² # a*b = [(a+b)² - (a²+b²)] / 2 prod = (missing_sum * missing_sum - missing_sq) // 2 # Solve quadratic: t² - (a+b)t + ab == 0 # discriminant = (a + b)² - 4ab D = missing_sum * missing_sum - 4 * prod root_D = int(D ** 0.5) while (root_D + 1) * (root_D + 1) <= D: root_D += 1 while root_D * root_D > D: root_D -= 1 a = (missing_sum - root_D) // 2 b = missing_sum - a return {a, b} # quick sanity checks if __name__ == "__main__": import random assert find_two_missing([], 2) == {0, 1} assert find_two_missing([0], 3) == {1, 2} assert find_two_missing([1], 3) == {0, 2} assert find_two_missing([2], 3) == {0, 1} assert find_two_missing([1, 2], 4) == {0, 3} assert find_two_missing([4, 2, 0], 5) == {1, 3} assert find_two_missing([0, 1, 2, 5], 6) == {3, 4} assert find_two_missing([5, 2, 1, 0], 6) == {3, 4} def test(): for n in range(2, 101): numbers = list(range(n)) random.shuffle(numbers) real_missing_numbers = {numbers.pop() for _ in range(2)} random.shuffle(numbers) missing_numbers = find_two_missing(numbers, n) assert real_missing_numbers == missing_numbers, f"Test failed for {n=}. Expected {real_missing_numbers}, got {missing_numbers} for {numbers=}" test() print("All tests passed!")

Solution by Anonymous User #51 (0.3 seconds)

def find_two_missing(numbers: list[int], n: int) -> set[int]: """ Finds two missing numbers from a list of integers from 0 to n-1 using Bit Manipulation. 1. XOR all numbers from 0 to n-1. 2. XOR all numbers present in the input list. 3. The result is x ^ y. 4. Find a set bit in x ^ y. 5. Partition the numbers into two groups based on this bit. 6. XOR the groups to find x and y. """ xor_all = 0 # XOR all numbers from 0 to n-1 for i in range(n): xor_all ^= i # XOR with numbers present in the list for num in numbers: xor_all ^= num # At this point, xor_all = x ^ y # Find the rightmost set bit (a differing bit between x and y) # Using x & -x to isolate the lowest set bit set_bit = xor_all & -xor_all missing_a = 0 missing_b = 0 # Iterate through the range and list to partition for i in range(n): if i & set_bit: missing_a ^= i else: missing_b ^= i for num in numbers: if num & set_bit: missing_a ^= num else: missing_b ^= num return {missing_a, missing_b}

New Solutions

Solution by Anonymous User #51 (0.3 seconds)

Solution by Anonymous User #43 (0.2 seconds)

Solution by Tom (0.2 seconds)

def find_two_missing(numbers: list[int], n: int) -> set[int]: return set(range(n)) - set(numbers)

Solution by Tom (0.2 seconds)

def find_two_missing(numbers: list[int], n: int) -> set[int]: seen = [False] * n for number in numbers: seen[number] = True unseen_numbers = {i for i in range(n) if not seen[i]} return unseen_numbers

Solution by Anonymous User #42 (0.2 seconds)