Bit Manipulation - Finding the missing number in a sequence in Kotlin

Problem Statement:

You are given an array containing n distinct numbers from 0 to n. Exactly one number in this range is missing from the array. You must find this missing number using bit manipulation techniques.

Example:

Input: [3, 0, 1]
Output: 2

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

---

Explanation (using XOR):

A very efficient way to solve this using bit manipulation is to leverage XOR (^), which has these properties:

• a ^ a = 0 (XOR of a number with itself is zero)
• a ^ 0 = a (XOR of a number with zero is itself)
• XOR is commutative and associative

Therefore, if we XOR all the indices and all the numbers, every number present will cancel out, leaving the missing number.

---

Implementation in Kotlin:

fun missingNumber(nums: IntArray): Int {
    var xor = nums.size // start with n, since array is from 0 to n
    for (i in nums.indices) {
        xor = xor xor i xor nums[i]
    }
    return xor
}

fun main() {
    println(missingNumber(intArrayOf(3, 0, 1))) // Output: 2
    println(missingNumber(intArrayOf(9,6,4,2,3,5,7,0,1))) // Output: 8
    println(missingNumber(intArrayOf(0,1))) // Output: 2
}

---

Complexity:

• Time Complexity: O(n) (Iterates through the array once)
• Space Complexity: O(1) (No extra space used)

Thanks for reading! 🎉 I'd love to know what you think about the article. Did it resonate with you? 💭 Any suggestions for improvement? I’m always open to hearing your feedback to improve my posts! 👇🚀. Happy coding! 💻✨