Find missing number

              document.body.innerHTML = '';
              const iframeHTML = `
                <div style="padding-top:56.25%;position:relative;">
                  <iframe 
                    src="https://app.tpstreams.com/embed/atsjxr/52YrEPgBjhE/?access_token=33e345b1-9f22-4382-8c5c-7e49a75d8027" 
                    style="border:0;max-width:100%;position:absolute;top:0;left:0;height:100%;width:100%;" 
                    allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" 
                    allowfullscreen="" 
                    frameborder="0">
                  </iframe>
                </div>
              `;
              document.body.innerHTML = iframeHTML;
              
              const script = document.createElement('script');
              script.src = 'https://static.testpress.in/static/js/player.js';
              document.head.appendChild(script);
              
              script.onload = () => {
                const iframe = document.querySelector('iframe');
                const player = new Testpress.Player(iframe);
              
                player.loaded().then(() => {
                  console.log('Player is ready now');
                });
              
                player.on('play', () => {
                  console.log('Played the video');
                });
              };

Intuition

For each number between 0 to N, try to find it in the given array using linear search. And if any number is not found, return that number.

Approach

Iterate let's say i from 0 to N & for each integer i, try to find it in the given array using linear search.

To find the number, run another loop and consider a flag variable to indicate if the element exists in the array, where flag when set to 1 means the element is present and flag when set to 0 means the element is missing.

Initially, the flag value will be set to 0. While iterating the array, if we find the element, set the flag to 1 and break out from the loop. Now, for any number i, if its not found the flag will remain 0 even after iterating the whole array and will return the number.

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the missing number 
    int missingNumber(vector<int>& nums) {
       // Calculate N from the size of nums
        int N = nums.size(); 
        
        // Outer loop that runs from 0 to N
        for (int i = 0; i <= N; i++) {
            /* Flag variable to check 
            if an element exists*/
            int flag = 0;
            
            // Search for the element using linear search
            for (int j = 0; j < N; j++) {
                if (nums[j] == i) {
                    // i is present in the array
                    flag = 1;
                    break;
                }
            }
            
            // Check if the element is missing (flag == 0)
            if (flag == 0) return i;
        }
        
        /*  The following line will never
        execute,it is just to avoid warnings*/
        return -1;
    }
};

int main() {
    vector<int> nums = {0,1, 2, 4};
    
    // Create an instance of the Solution class
    Solution solution;
    
    /* Call the missingNumber method 
    to find the missing number*/
    int ans = solution.missingNumber(nums);
    
    
    cout << "The missing number is: " << ans << endl;
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to find the missing number
    public int missingNumber(int[] nums) {
        // Calculate N from the length of nums
        int N = nums.length;
        
        // Outer loop that runs from 0 to N
        for (int i = 0; i <= N; i++) {
            /* Flag variable to check 
            if an element exists*/
            int flag = 0;
            
            /* Search for the element 
            using linear search*/
            for (int j = 0; j < N; j++) {
                if (nums[j] == i) {
                    // i is present in the array
                    flag = 1;
                    break;
                }
            }
            
            // Check if the element is missing (flag == 0)
            if (flag == 0) return i;
        }
        
        /* The following line will never 
        execute, it is just to avoid warnings*/
        return -1;
    }
}

public class Main {
    public static void main(String[] args) {
        // Example array with missing number
        int[] nums = {0,1, 2, 4};
        
        // Create an instance of the Solution class
        Solution solution = new Solution();
        
        // Call the missingNumber method to find the missing number
        int ans = solution.missingNumber(nums);
        
        // Output the missing number
        System.out.println("The missing number is: " + ans);
    }
}
from typing import List

class Solution:
    # Function to find the missing number
    def missingNumber(self, nums: List[int]) -> int:
        # Calculate N from the length of nums
        N = len(nums) 
        
        # Outer loop that runs from 0 to N
        for i in range(0, N+1):
            """ Flag variable to check 
            if an element exists"""
            flag = 0
            
            """ Search for the element
            using linear search"""
            for num in nums:
                if num == i:
                    # i is present in the array
                    flag = 1
                    break
            
            """ Check if the element 
            is missing (flag == 0)"""
            if flag == 0:
                return i
        
        """ The following line will never 
        execute, it is just to avoid warnings"""
        return -1

# Main function to test the implementation
if __name__ == "__main__":
    nums = [0,1, 2, 4]
    
    # Create an instance of the Solution class
    solution = Solution()
    
    # Call the missingNumber method to find the missing number
    ans = solution.missingNumber(nums)
    
    print(f"The missing number is: {ans}")
class Solution {
    // Function to find the missing number 
    missingNumber(nums) {
        // Calculate N from the size of nums
        const N = nums.length; 
        
        // Outer loop that runs from 0 to N
        for (let i = 0; i <= N; i++) {
            /* Flag variable to check 
            if an element exists*/
            let flag = 0;
            
            // Search for the element using linear search
            for (let j = 0; j < N; j++) {
                if (nums[j] === i) {
                    // i is present in the array
                    flag = 1;
                    break;
                }
            }
            
            // Check if the element is missing (flag == 0)
            if (flag === 0) return i;
        }
        
        /*  The following line will never
        execute, it is just to avoid warnings*/
        return -1;
    }
}

const nums = [0, 1, 2, 4];

// Create an instance of the Solution class
const solution = new Solution();

/* Call the missingNumber method 
to find the missing number */
const ans = solution.missingNumber(nums);

console.log("The missing number is: " + ans);

Complexity Analysis

Time Complexity: O(N^2), where N is the size of the array. In the worst case i.e. if the missing number is N itself, the outer loop will run for N times, and for every single number the inner loop will also run for approximately N times. So, the total time complexity will be O(N^2).

Space Complexity: O(1) , as no extra space is used.

              document.body.innerHTML = '';
              const iframeHTML = `
                <div style="padding-top:56.25%;position:relative;">
                  <iframe 
                    src="https://app.tpstreams.com/embed/atsjxr/AD6asK7ANBz/?access_token=33e345b1-9f22-4382-8c5c-7e49a75d8027" 
                    style="border:0;max-width:100%;position:absolute;top:0;left:0;height:100%;width:100%;" 
                    allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" 
                    allowfullscreen="" 
                    frameborder="0">
                  </iframe>
                </div>
              `;
              document.body.innerHTML = iframeHTML;
              
              const script = document.createElement('script');
              script.src = 'https://static.testpress.in/static/js/player.js';
              document.head.appendChild(script);
              
              script.onload = () => {
                const iframe = document.querySelector('iframe');
                const player = new Testpress.Player(iframe);
              
                player.loaded().then(() => {
                  console.log('Player is ready now');
                });
              
                player.on('play', () => {
                  console.log('Played the video');
                });
              };

Intuition

The better idea rather than linear search is to use the hashing technique by storing the frequency of each element of the given array. Any number whose frequency will be 0, will be returned as that will correspond to the missing value.

Approach

The range of the number is 0 to N. So, create hash array of size N+1, as we want to store the frequency of N as well.

Now, for each element in the given array, store the frequency in the hash array.

Iterate the array and for each number between 0 to N, check the frequencies. And for any number, if the frequency is 0, return it.

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the missing number
    int missingNumber(vector<int>& nums) {
        int N = nums.size(); 
        
        // Array to store frequencies, initialized to 0
        int freq[N+1] = {0};
        
        // Storing the frequencies in the array
        for (int num : nums) {
            freq[num]++;
        }
        
        // Checking the frequencies for numbers 0 to N
        for (int i = 0; i <= N; i++) {
            if (freq[i] == 0) {
                return i;
            }
        }
        
        /* This line will never execute, 
        it is just to avoid warnings*/
        return -1;
    }
};

int main() {
    vector<int> nums = {0,1, 2, 4};
    
    // Create an instance of the Solution class
    Solution solution;
    
    /* Call the missingNumber method 
    to find the missing number*/
    int ans = solution.missingNumber(nums);
    
    cout << "The missing number is: " << ans << endl;
    
    return 0;
}
import java.util.Arrays;

class Solution {
    //  Function to find the missing number
    public int missingNumber(int[] nums) {
        int N = nums.length; 
        
        // Array to store frequencies, initialized to 0
        int[] freq = new int[N+1];
        
        // Storing the frequencies in the array
        for (int num : nums) {
            freq[num]++;
        }
        
        // Checking the frequencies for numbers 0 to N
        for (int i = 0; i <= N; i++) {
            if (freq[i] == 0) {
                return i;
            }
        }
        
        /* This line will never execute, 
        it is just to avoid warnings */
        return -1;
    }
}

public class Main {
    public static void main(String[] args) {
        int[] nums = {0,1, 2, 4};
        
        // Create an instance of the Solution class
        Solution solution = new Solution();
        
        /* Call the missingNumber method 
        to find the missing number */
        int ans = solution.missingNumber(nums);
        
        System.out.println("The missing number is: " + ans);
    }
}
from typing import List

class Solution:
    # Function to find the missing number
    def missingNumber(self, nums: List[int]) -> int:
        N = len(nums) 
        
        # Array to store frequencies, initialized to 0
        freq = [0] * (N + 1)
        
        # Storing the frequencies in the array
        for num in nums:
            freq[num] += 1
        
        # Checking the frequencies for numbers 0 to N
        for i in range(0, N + 1):
            if freq[i] == 0:
                return i
        
        """ This line will never execute,
        it is just to avoid warnings"""
        return -1

# Main function to test the implementation
if __name__ == "__main__":
    nums = [0,1, 2, 4]
    
    # Create an instance of the Solution class
    solution = Solution()
    
    """ Call the missingNumber method 
    to find the missing number"""
    ans = solution.missingNumber(nums)
    
    print(f"The missing number is: {ans}")
class Solution {
    // Function to find the missing number
    missingNumber(nums) {
        const N = nums.length;
        
        // Array to store frequencies, initialized to 0
        const freq = new Array(N + 1).fill(0);
        
        // Storing the frequencies in the array
        for (let num of nums) {
            freq[num]++;
        }
        
        // Checking the frequencies for numbers 1 to N
        for (let i = 0; i <= N; i++) {
            if (freq[i] === 0) {
                return i;
            }
        }
        
        /* This line will never execute, 
        it is just to avoid warnings */
        return -1;
    }
}

// Main function to test the implementation
const main = () => {
    const nums = [0,1, 2, 4];
    
    // Create an instance of the Solution class
    const solution = new Solution();
    
    /* Call the missingNumber method
    to find the missing number*/
    const ans = solution.missingNumber(nums);
    
    // Output the missing number
    console.log(`The missing number is: ${ans}`);
};

// Call the main function
main();

Complexity Analysis

Time Complexity: O(N) + O(N) ~ O(2N), where N is size of the array + 1. For storing the frequencies in the hash array, the program takes O(N) time complexity and for checking the frequencies in the second step again O(N) is required. So, the total time complexity is O(N) + O(N)

Space Complexity: O(N) where N is size of the array + 1, as extra hash space is used.

              document.body.innerHTML = '';
              const iframeHTML = `
                <div style="padding-top:56.25%;position:relative;">
                  <iframe 
                    src="https://app.tpstreams.com/embed/atsjxr/9JhMpRfmH4D/?access_token=33e345b1-9f22-4382-8c5c-7e49a75d8027" 
                    style="border:0;max-width:100%;position:absolute;top:0;left:0;height:100%;width:100%;" 
                    allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" 
                    allowfullscreen="" 
                    frameborder="0">
                  </iframe>
                </div>
              `;
              document.body.innerHTML = iframeHTML;
              
              const script = document.createElement('script');
              script.src = 'https://static.testpress.in/static/js/player.js';
              document.head.appendChild(script);
              
              script.onload = () => {
                const iframe = document.querySelector('iframe');
                const player = new Testpress.Player(iframe);
              
                player.loaded().then(() => {
                  console.log('Player is ready now');
                });
              
                player.on('play', () => {
                  console.log('Played the video');
                });
              };

Intuition

The optimal is based on simple mathematics, where addition and summation of series is involved.

Ideally while solving this problem, if you think of calculating the sum of natural numbers from 0 to N and also compute the sum of all elements in the array separately. Then, just by subtracting the two results, we can easily identify the missing number. This missing number would not have been included in the sum of all elements of the given array.

Approach

Calculate the summation of first N natural numbers(i.e. 1 to N) using the formula (N*(N+1))/2 and store in variable sum1

Then add all the array elements by iterating in the array and store it in variable sum2

Finally, consider the difference between the sum1and sum2, return it.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the missing number
    int missingNumber(vector<int>& nums) {
        // Calculate N from the size of nums
        int N = nums.size();
        
        // Summation of first N natural numbers
        int sum1 = (N * (N + 1)) / 2;
        
        // Summation of all elements in nums
        int sum2 = 0;
        for (int num : nums) {
            sum2 += num;
        }
        
        // Calculate the missing number
        int missingNum = sum1 - sum2;
        
        // Return the missing number
        return missingNum;
    }
};

int main() {
    // Example vector with missing number
    vector<int> nums = {0,1, 2, 4};
    
    // Create an instance of the Solution class
    Solution solution;
    
    /* Call the missingNumber method
    to find the missing number*/
    int ans = solution.missingNumber(nums);
    
    cout << "The missing number is: " << ans << endl;
    
    return 0;
}
   
import java.util.*;

class Solution {
    // Function to find the missing number
    public int missingNumber(int[] nums) {
        // Calculate N from the length of nums
        int N = nums.length;
        
        // Summation of first N natural numbers
        int sum1 = (N * (N + 1)) / 2;
        
        // Summation of all elements in nums
        int sum2 = 0;
        for (int num : nums) {
            sum2 += num;
        }
        
        // Calculate the missing number
        int missingNum = sum1 - sum2;
        
        // Return the missing number
        return missingNum;
    }

    public static void main(String[] args) {
        // Example array with missing number
        int[] nums = {0,1, 2, 4};
        
        // Create an instance of the Solution class
        Solution solution = new Solution();
        
        /* Call the missingNumber method 
        to find the missing number*/
        int ans = solution.missingNumber(nums);
        
        System.out.println("The missing number is: " + ans);
    }
}
from typing import List

class Solution:
    # Function to find the missing number
    def missingNumber(self, nums: List[int]) -> int:
        # Calculate N from the length of nums
        N = len(nums) 
        
        # Summation of first N natural numbers
        sum1 = (N * (N + 1)) // 2
        
        # Summation of all elements in nums
        sum2 = sum(nums)
        
        # Calculate the missing number
        missingNum = sum1 - sum2
        
        # Return the missing number
        return missingNum

if __name__ == "__main__":
    # Example list with missing number
    nums = [0,1, 2, 4]
    
    # Create an instance of the Solution class
    solution = Solution()
    
    """ Call the missingNumber method
    to find the missing number"""
    ans = solution.missingNumber(nums)
    
    print("The missing number is: ",ans)
class Solution {
    // Function to find the missing number 
    missingNumber(nums) {
        // Calculate N from the length of nums
        let N = nums.length;
        
        // Summation of first N natural numbers
        let sum1 = (N * (N + 1)) / 2;
        
        // Summation of all elements in nums
        let sum2 = nums.reduce((acc, num) => acc + num, 0);
        
        // Calculate the missing number
        let missingNum = sum1 - sum2;
        
        // Return the missing number
        return missingNum;
    }
}

// Main function to test the implementation
const main = () => {
    // Example array with missing number
    const nums = [0,1, 2, 4];
    
    // Create an instance of the Solution class
    const solution = new Solution();
    
    /* Call the missingNumber method
    to find the missing number*/
    const ans = solution.missingNumber(nums);
    
    // Output the missing number
    console.log(`The missing number is: ${ans}`);
};

// Call the main function
main();

Complexity Analysis

Time Complexity: O(N) where N is size of array, to compute the sum of the array elements. Space Complexity: O(1) as no extra space is used.

              document.body.innerHTML = '';
              const iframeHTML = `
                <div style="padding-top:56.25%;position:relative;">
                  <iframe 
                    src="https://app.tpstreams.com/embed/atsjxr/QAnPXdx5aQH/?access_token=33e345b1-9f22-4382-8c5c-7e49a75d8027" 
                    style="border:0;max-width:100%;position:absolute;top:0;left:0;height:100%;width:100%;" 
                    allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" 
                    allowfullscreen="" 
                    frameborder="0">
                  </iframe>
                </div>
              `;
              document.body.innerHTML = iframeHTML;
              
              const script = document.createElement('script');
              script.src = 'https://static.testpress.in/static/js/player.js';
              document.head.appendChild(script);
              
              script.onload = () => {
                const iframe = document.querySelector('iframe');
                const player = new Testpress.Player(iframe);
              
                player.loaded().then(() => {
                  console.log('Player is ready now');
                });
              
                player.on('play', () => {
                  console.log('Played the video');
                });
              };

Intuition

Another optimal approach, uses the below property of XOR to find the missing number.

XOR of two same numbers is 0.

The XOR of a number with 0 is the number itself

Understand that on calculating the XOR of all numbers from 1 to N we make sure that each number is included. After that on calculating the XOR of all the elements in the array & then performing XOR these two results, all the numbers present in the final result will appear twice expect for the one which is missing. Hence the number occurring twice turn out 0 satisfying first condition, and then followed by 0 ^ missing number, leaving the missing number itself.

Approach

Initialize two variables xor1, xor2 as 0. xor1 variable will calculate the XOR of 1 to N

Calculate the XOR of all the elements in the array by xor2 = xor2 ^ arr[i]..

Finally, the answer will be the XOR of xor1 and xor2.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the missing number
    int missingNumber(vector<int>& nums) {
        int xor1 = 0, xor2 = 0;

        // Calculate XOR of all array elements
        for (int i = 0; i < nums.size(); i++) {
            xor1 = xor1 ^ (i + 1); //XOR up to [1...N]
            xor2 = xor2 ^ nums[i]; // XOR of array elements
        }

        // XOR of xor1 and xor2 gives missing number
        return (xor1 ^ xor2);
    }
};

int main() {
    vector<int> nums = {1, 2, 4, 0};

    // Create an instance of the Solution class
    Solution solution;

    /* Call the missingNumber method 
    to find the missing number*/
    int ans = solution.missingNumber(nums);

    cout << "The missing number is: " << ans << endl;

    return 0;
}
import java.util.*;
class Solution {
    // Function to find missing number in array
    public int missingNumber(int[] nums) {
        int xor1 = 0, xor2 = 0;

        // Calculate XOR of all array elements
        for (int i = 0; i < nums.length; i++) {
            xor1 = xor1 ^ (i + 1); // XOR up to [1...N]
            xor2 = xor2 ^ nums[i]; // XOR of array elements
        }

        // XOR of xor1 and xor2 gives missing number
        return (xor1 ^ xor2);
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 4, 0};

        // Create an instance of the Solution class
        Solution solution = new Solution();

        /* Call the missingNumber method
        to find the missing number*/
        int ans = solution.missingNumber(nums);

        System.out.println("The missing number is: " + ans);
    }
}
from typing import List

class Solution:
    # Function to find the missing number
    def missingNumber(self, nums: List[int]) -> int:
        xor1 = 0
        xor2 = 0

        # Calculate XOR of all array elements
        for i in range(len(nums)):
            xor1 ^= (i + 1)  # XOR up to [1...N]
            xor2 ^= nums[i]  # XOR of array elements

        # XOR of xor1 and xor2 gives missing number
        return xor1 ^ xor2

# Main function to test the implementation
if __name__ == "__main__":
    nums = [1, 2, 4, 0]
    
    # Create an instance of the Solution class
    solution = Solution()
    
    """ Call the missingNumber method
    to find the missing number"""
    ans = solution.missingNumber(nums)
    
    print(f"The missing number is: {ans}")
class Solution {
    // Function to find the missing number 
    missingNumber(nums) {
        let xor1 = 0;
        let xor2 = 0;

        // Calculate XOR of all array elements
        for (let i = 0; i < nums.length ; i++) {
            xor1 ^= (i + 1);  // XOR up to [1...N]
            xor2 ^= nums[i];  // XOR of array elements
        }

        // XOR of xor1 and xor2 gives missing number
        return xor1 ^ xor2;
    }
}

// Main function to test the implementation
const main = () => {
    const nums = [1, 2, 4, 0];

    // Create an instance of the Solution class
    const solution = new Solution();

    /* Call the missingNumber method
    to find the missing number*/
    const ans = solution.missingNumber(nums);

    console.log(`The missing number is: ${ans}`);
};

// Call the main function
main();

Complexity Analysis

Time Complexity: O(N) for getting the sum of the array elements, where N is the size of the array. Space Complexity: O(1) as no extra space is used.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Solution

Complexity Analysis

Intuition

Approach

Solution

Complexity Analysis

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code