Finding the missing number in an array

by

Finding the missing number in an array containing n distinct numbers taken from 0, 1, 2, ..., n is a classic problem that can be efficiently solved using bit manipulation. The idea is to use the XOR operation, which has two useful properties for this problem:

  1. XOR of a number with itself is 0: a XOR a = 0
  2. XOR of a number with 0 is the number itself: a XOR 0 = a

Given these properties, you can XOR all the numbers in the given array with all the numbers from 0 to n. Since there is exactly one number missing in the array, the result of XORing everything together will be that missing number. This works because the XOR operation is commutative and associative, and every number from 0 to n except the missing number will be XORed with itself and thus cancel out to 0, leaving only the missing number.

Here’s how you can find the missing number in Kotlin:

Kotlin
fun missingNumber(nums: IntArray): Int {
    var xor = 0
    // XOR all numbers from 1 to n
    for (i in 1..nums.size) {
        xor = xor xor i
    }
    // XOR the result with all numbers in the array
    for (num in nums) {
        xor = xor xor num
    }
    return xor
}

fun main() {
    val nums = intArrayOf(3, 0, 1)
    println("The missing number is: ${missingNumber(nums)}")
}

Explanation:

  • XOR from 1 to n: The first loop XORs all numbers from 1 to n (inclusive), where n is the size of the array. This effectively sets up the xor variable to be the result of XORing all numbers that should be in the array.
  • XOR with Array Elements: The second loop XORs xor with each number in the array. Since the XOR operation cancels out identical numbers (due to the property that a XOR a = 0), and every number from 0 to n except the missing one appears in the array, the final value of xor after this loop will be the missing number.
  • Return Missing Number: The function returns xor, which now holds the missing number.

This approach is efficient because it requires only a single pass through the array and operates in linear time (O(n)), with constant extra space (O(1)), making it an optimal solution for finding the missing number in the array.

Leave a Comment