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.
1using System;
2
3public class Solution {
4 public int MissingNumber(int[] nums) {
5 int n = nums.Length;
6 int total = n * (n + 1) / 2;
7 int sum = 0;
8 foreach (int num in nums) {
9 sum += num;
10 }
11 return total - sum;
12 }
13
14 public static void Main(string[] args) {
15 int[] nums = {3, 0, 1};
16 Solution sol = new Solution();
17 Console.WriteLine("Missing number: " + sol.MissingNumber(nums));
18 }
19}This C# program uses the arithmetic sum formula and iterative summation over the array to find the missing number, demonstrating similar logic to other language solutions.
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.
1class Solution {
2 public int missingNumber(int[] nums) {
3 int xorResult = 0;
4 for (int i = 0; i < nums.length; i++) {
5 xorResult ^= i ^ nums[i];
6 }
7 xorResult ^= nums.length;
8 return xorResult;
9 }
10
11 public static void main(String[] args) {
12 Solution sol = new Solution();
13 int[] nums = {3, 0, 1};
14 System.out.println("Missing number: " + sol.missingNumber(nums));
15 }
16}Java solution employs bit manipulation with XOR to successfully find the missing element without extra space, performing operations in O(n) time.