Finding the Missing Number in a Sequence

The "Missing Number" problem is a classic example of array and bit manipulation in computer science. It involves finding a missing number in a sequence.

Problem Statement

Given an array containing n distinct numbers taken from 0 to n, find the one number that is missing from the sequence.

Examples

• Input: nums = [3,0,1] Output: 2 Explanation: Numbers 0, 1, and 3 are present. The missing number is 2.

• Input: nums = [0,1] Output: 2 Explanation: Numbers 0 and 1 are present. The missing number is 2.

Solutions

Mathematical Solution:

Bit Manipulation Solution:

Breaking Down the Solutions

• Mathematical Approach:
  • The sum of the first n numbers is n * (n + 1) / 2. We can use this formula to find the expected sum of the numbers in the array.
  • We can then find the actual sum of the numbers in the array by using the reduce method.
  • The difference between the expected sum and the actual sum is the missing number.
• Bit Manipulation Approach:
  • We can use the XOR operator to find the missing number.
  • The XOR operator is a bitwise operator that returns a 1 if the bits are different and a 0 if the bits are the same.
  • We can use the XOR operator to find the missing number by XORing the index of each number in the array with the number itself.
  • The XOR operator is associative and commutative, so we can XOR the numbers in any order.
  • We can XOR the index of each number in the array with the number itself to find the missing number.

Conclusion

The "Missing Number" problem is a classic example of array and bit manipulation in computer science. It involves finding a missing number in a sequence. We can solve this problem using mathematical and bit manipulation techniques.

Rust Solution

Rust's nums.len() returns a usize, so n needs the as i32 cast before it can multiply into the i32 the function returns and subtract cleanly at the end. The let actual: i32 annotation is load-bearing rather than cosmetic: nums.iter().sum() is generic over its accumulator type, so the compiler leans on that annotation to know it should sum into an i32. Because the trailing expected - actual carries no semicolon, it is the function's tail expression and stands in for an explicit return.

Go Solution

Go's len(nums) already hands back an int, so the arithmetic needs no cast — contrast the Rust version's as i32. There is no standard-library fold here: actual is seeded with := to 0 and accumulated inside a for _, x := range nums loop, where range yields an index and value each step and the blank identifier _ discards the index since only the values x are summed.