algoadvance

Leetcode 268. Missing Number

Problem Statement

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

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

Example 2:

Input: nums = [0,1]
Output: 2

Example 3:

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

Constraints:

• n == nums.length
• 1 <= n <= 10^4
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

Clarifying Questions

1. Is the input array always guaranteed to have a missing number? Yes, the problem guarantees that one number in the range [0, n] is missing.

2. Can the input array be empty? No, according to the constraints, n >= 1.

Strategy

1. Mathematical Approach:
   • Calculate the expected sum of the first n natural numbers using the formula n * (n + 1) / 2.
   • Calculate the actual sum of the elements in the array.
   • The difference between the expected sum and the actual sum will yield the missing number.

Time Complexity

• Time Complexity: O(n) - We only need a single pass through the array to calculate the sum.
• Space Complexity: O(1) - We use a constant amount of space.

Code

public class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        // Sum of first `n` natural numbers
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        
        // Calculate the sum of elements in the array
        for (int num : nums) {
            actualSum += num;
        }
        
        // The missing number is the difference between expected and actual sums
        return expectedSum - actualSum;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // Test cases
        int[] testCase1 = {3, 0, 1};
        System.out.println(solution.missingNumber(testCase1)); // Output: 2

        int[] testCase2 = {0, 1};
        System.out.println(solution.missingNumber(testCase2)); // Output: 2
        
        int[] testCase3 = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println(solution.missingNumber(testCase3)); // Output: 8
    }
}

This solution calculates the expected sum of numbers from 0 to n, then subtracts the actual sum of the numbers in the array from it to find the missing number. This method is efficient and direct.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?