CSES Solutions - Missing Number

Given an array arr[] of size N - 1 containing numbers between 1, 2... N, except one, the task is to find the missing number.

Examples:

Input: N = 5, arr[] = {2, 3, 1, 5}
Output: 4
Explanation: arr[] contains all numbers from 1 to 5 except 4, therefore the answer is 4.

Input: N = 6, arr[] = {4, 5, 1, 2, 3}
Output: 6
Explanation: arr[] contains all numbers from 1 to 6 except 6, therefore the answer is 6.

Approach: To solve the problem, follow the below idea:

The problem can be solved using bitwise XOR operation. We can take the XOR of all the elements of arr[] and all numbers from 1 to N. Except for the missing number, every number from 1 to N will occur two times: once in arr[] and once while iterating from 1 to N. Since taking XOR of any number with itself leads to 0, so the XOR of all the numbers which occur two times will become 0 leaving behind the only number which occurred once while iterating from 1 to N but not in arr[].

Step-by-step algorithm:

• Initialize a variable XOR to store the bitwise XOR of all the elements of arr[] and all the numbers from 1 to N.
• After taking the XOR of all the numbers and elements of arr[], the missing number is equal to XOR.
• Return XOR as the answer.

Below is the implementation of the algorithm:

#include <bits/stdc++.h> using namespace std; // function to find the missing number from 1 to N int solve(int N, int* arr) {  // Variable to store the value of XOR  int XOR = 0;  for (int i = 0; i < N - 1; i++) {  // XOR of all elements in arr[]  XOR ^= arr[i];  // XOR of all numbers from 1 to N - 1  XOR ^= (i + 1);  }  XOR ^= N;  return XOR; } int main() {  // Sample Input  int N = 5;  int arr[] = {2, 3, 1, 5};  cout << solve(N, arr) << "\n";  return 0; } 

import java.util.*; public class Main {  // Function to find the missing number from 1 to N  static int solve(int N, int[] arr) {  // Variable to store the value of XOR  int XOR = 0;  for (int i = 0; i < N - 1; i++) {  // XOR of all elements in arr[]  XOR ^= arr[i];  // XOR of all numbers from 1 to N - 1  XOR ^= (i + 1);  }  // XOR of all elements in arr[] and all numbers from 1 to N  XOR ^= N;  return XOR;  }  public static void main(String[] args) {  // Sample Input  int N = 5;  int[] arr = {2, 3, 1, 5};  System.out.println(solve(N, arr));  } } 

# Function to find the missing number from 1 to N def solve(N, arr): # Variable to store the value of XOR XOR = 0 for i in range(N - 1): # XOR of all elements in arr[] XOR ^= arr[i] # XOR of all numbers from 1 to N - 1 XOR ^= (i + 1) XOR ^= N return XOR if __name__ == "__main__": # Sample Input N = 5 arr = [2, 3, 1, 5] print(solve(N, arr)) # This code is contributed by shivamgupt310570 

using System; class Program {  // Function to find the missing number from 1 to N  static int Solve(int N, int[] arr)  {  // Variable to store the value of XOR  int XOR = 0;  for (int i = 0; i < N - 1; i++) {  // XOR of all elements in arr[]  XOR ^= arr[i];  // XOR of all numbers from 1 to N - 1  XOR ^= (i + 1);  }  XOR ^= N;  return XOR;  }  static void Main(string[] args)  {  // Sample Input  int N = 5;  int[] arr = { 2, 3, 1, 5 };  // Function Call  Console.WriteLine(Solve(N, arr));  } } 

// Function to find the missing number from 1 to N function solve(N, arr) {  // Variable to store the value of XOR  let XOR = 0;  for (let i = 0; i < N - 1; i++) {  // XOR of all elements in arr[]  XOR ^= arr[i];  // XOR of all numbers from 1 to N - 1  XOR ^= (i + 1);  }  // XOR of all elements in arr[] and all numbers from 1 to N  XOR ^= N;  return XOR; } // Main function function main() {  // Sample Input  const N = 5;  const arr = [2, 3, 1, 5];  // Call the solve function and print the result  console.log(solve(N, arr)); } // Invoke the main function main(); 

4 

Time Complexity: O(N), where N is the size of array arr[].
Auxiliary Space: O(1)

Approach2 (Using Direct Formula approach)

In this approach we will create Function to find the missing number using the sum of natural numbers formula. First we will Calculate the total sum of the first N natural numbers using formula n * (n + 1) / 2. Now we calculate sum of all elements in given array. Subtract the total sum with sum of all elements in given array and return the missing number.

Example : To demonstrate finding the missing number Using Direct Formula approach

#include <iostream> #include <vector> using namespace std; int findMissingNumber(const vector<int>& nums) {  // Calculate the total sum  int n = nums.size() + 1;  int totalSum = n * (n + 1) / 2;  // Calculate sum of all elements in the given array  int arraySum = 0;  for (int num : nums) {  arraySum += num;  }  // Subtract and return the total sum with the sum of  // all elements in the array  int missingNumber = totalSum - arraySum;  return missingNumber; } int main() {  vector<int> numbers = { 1, 2, 4, 5, 6 };  cout << findMissingNumber(numbers);  return 0; } 

import java.util.ArrayList; import java.util.List; class Main {  static int findMissingNumber(List<Integer> nums)  {  // Calculate the total sum  int n = nums.size() + 1;  int totalSum = n * (n + 1) / 2;  // Calculate sum of all elements in the given list  int arraySum = 0;  for (int num : nums) {  arraySum += num;  }  // Subtract and return the total sum with the sum of  // all elements in the list  int missingNumber = totalSum - arraySum;  return missingNumber;  }  public static void main(String[] args)  {  List<Integer> numbers = new ArrayList<>();  numbers.add(1);  numbers.add(2);  numbers.add(4);  numbers.add(5);  numbers.add(6);  System.out.println(findMissingNumber(numbers));  } } // This code is contributed by Monu. 

def find_missing_number(nums): # Calculate the total sum n = len(nums) + 1 total_sum = n * (n + 1) // 2 # Calculate sum of all elements in the given list array_sum = sum(nums) # Subtract and return the total sum with the sum of all elements in the list missing_number = total_sum - array_sum return missing_number if __name__ == "__main__": numbers = [1, 2, 4, 5, 6] print(find_missing_number(numbers)) 

function findMissingNumber(nums) {  // Calculate the total sum  const n = nums.length + 1;  const totalSum = (n * (n + 1)) / 2;  // Calculate sum of all elements in the given array  let arraySum = 0;  for (let num of nums) {  arraySum += num;  }  // Subtract and return the total sum with the sum of all elements in the array  const missingNumber = totalSum - arraySum;  return missingNumber; } const numbers = [1, 2, 4, 5, 6]; console.log(findMissingNumber(numbers)); 

The missing number from the array is: 3 

Time Complexity: O(n)
Auxiliary Space: O(1)