Sponsored
Sponsored
This approach uses the formula for the sum of the first n natural numbers: Sum = n * (n + 1) / 2. By calculating the sum of the numbers from the array and subtracting it from the expected sum, we can find the missing number.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), as no additional space is used beyond variables.
1class Solution:
2 def missingNumber(self, nums):
3 n = len(nums)
4 total = n * (n + 1) // 2
5 return total - sum(nums)
6
7# Usage
8nums = [3, 0, 1]
9sol = Solution()
10print(f"Missing number: {sol.missingNumber(nums)}")This Python solution calculates the expected total using n * (n + 1) // 2 and uses the built-in sum() function to find the sum of the array. The missing number is found by subtracting these sums.
An efficient approach is using XOR. XORing a number with itself results in zero (n ^ n = 0), and XOR of any number with zero keeps the number unchanged (n ^ 0 = n). By XORing all indices and array elements together, each number present in both will cancel out, leaving the missing number.
Time Complexity: O(n), iterating through the array.
Space Complexity: O(1), using constant space.
1using System;
public class Solution {
public int MissingNumber(int[] nums) {
int xorResult = 0;
for (int i = 0; i < nums.Length; i++) {
xorResult ^= i ^ nums[i];
}
xorResult ^= nums.Length;
return xorResult;
}
public static void Main(string[] args) {
int[] nums = {3, 0, 1};
Solution sol = new Solution();
Console.WriteLine("Missing number: " + sol.MissingNumber(nums));
}
}This C# program leverages XOR properties to find the missing element by processing indices and numbers simultaneously.