Given an array of size n. It is also given that range of numbers is from smallestNumber to smallestNumber + n where smallestNumber is the smallest number in array. The array contains number in this range but one number is missing so the task is to find this missing number.
Examples:
Input: arr[] = {13, 12, 11, 15}
Output: 14Input: arr[] = {33, 36, 35, 34};
Output: 37
The problem is very close to find missing number.
There are many approaches to solve this problem.
A simple approach is to first find minimum, then one by one search all elements. Time complexity of this approach is O(n*n)
A better solution is to sort the array. Then traverse the array and find the first element which is not present. Time complexity of this approach is O(n Log n)
The best solution is to first XOR all the numbers. Then XOR this result to all numbers from smallest number to n+smallestNumber. The XOR is our result.
Example:
arr[n] = {13, 12, 11, 15} smallestNumber = 11 first find the xor of this array 13^12^11^15 = 5 Then find the XOR first number to first number + n 11^12^13^14^15 = 11; Then xor these two number's 5^11 = 14 // this is the missing number
Implementation:
C++
// CPP program to find missing // number in a range. #include <bits/stdc++.h> using namespace std; // Find the missing number // in a range int missingNum( int arr[], int n) { int minvalue = *min_element(arr, arr+n); // here we xor of all the number int xornum = 0; for ( int i = 0; i < n; i++) { xornum ^= (minvalue) ^ arr[i]; minvalue++; } // xor last number return xornum ^ minvalue; } // Driver code int main() { int arr[] = { 13, 12, 11, 15 }; int n = sizeof (arr)/ sizeof (arr[0]); cout << missingNum(arr, n); return 0; } |
Java
// Java program to find // missing number in a range. import java.io.*; import java.util.*; class GFG { // Find the missing number in a range static int missingNum( int arr[], int n) { List<Integer> list = new ArrayList<>(arr.length); for ( int i :arr) { list.add(Integer.valueOf(i)); } int minvalue = Collections.min(list);; // here we xor of all the number int xornum = 0 ; for ( int i = 0 ; i < n; i++) { xornum ^= (minvalue) ^ arr[i]; minvalue++; } // xor last number return xornum ^ minvalue; } public static void main (String[] args) { int arr[] = { 13 , 12 , 11 , 15 }; int n = arr.length; System.out.println(missingNum(arr, n)); } } //This code is contributed by Gitanjali. |
Python3
# python3 program to check # missingnumber in a range # Find the missing number # in a range def missingNum( arr, n): minvalue = min (arr) # here we xor of all the number xornum = 0 for i in range ( 0 ,n): xornum ^ = (minvalue) ^ arr[i] minvalue = minvalue + 1 # xor last number return xornum ^ minvalue # Driver method arr = [ 13 , 12 , 11 , 15 ] n = len (arr) print (missingNum(arr, n)) # This code is contributed by Gitanjali. |
C#
// C# program to find // missing number in a range. using System; using System.Collections.Generic; using System.Linq; class GFG { // Find the missing number in a range static int missingNum( int []arr, int n) { List< int > list = new List< int >(arr.Length); foreach ( int i in arr) { list.Add(i); } int minvalue = list.Min(); // here we xor of all the number int xornum = 0; for ( int i = 0; i < n; i++) { xornum ^= (minvalue) ^ arr[i]; minvalue++; } // xor last number return xornum ^ minvalue; } // Driver Code public static void Main (String[] args) { int []arr = { 13, 12, 11, 15 }; int n = arr.Length; Console.WriteLine(missingNum(arr, n)); } } // This code is contributed by Rajput-Ji |
PHP
<?php // PHP program to find missing // number in a range. // Find the missing number // in a range function missingNum( $arr , $n ) { $minvalue = min( $arr ); // here we xor of all the number $xornum = 0; for ( $i = 0; $i < $n ; $i ++) { $xornum ^= ( $minvalue ) ^ $arr [ $i ]; $minvalue ++; } // xor last number return $xornum ^ $minvalue ; } // Driver code $arr = array ( 13, 12, 11, 15 ); $n = sizeof( $arr ); echo missingNum( $arr , $n ); // This code is contributed // by Sach_Code ?> |
Javascript
<script> // Javascript program to find missing // number in a range. // Find the missing number // in a range function missingNum(arr, n) { let minvalue = Math.min(...arr); // here we xor of all the number let xornum = 0; for (let i = 0; i < n; i++) { xornum ^= (minvalue) ^ arr[i]; minvalue++; } // xor last number return xornum ^ minvalue; } // Driver code let arr = [ 13, 12, 11, 15 ]; let n = arr.length; document.write(missingNum(arr, n)); </script> |
14
Time Complexity: O(n), where n is the size of the array
Auxiliary Space: O(1)
Another Approach:
An efficient approach to find out the missing number can be performed using the concept that sum of the arithmetic progression smallestNumber, smallestNumber + 1, smallestNumber + 2, ….. , smallestNumber + n, which is (n + 1) x (2smallestNumber + 1) / 2 is equal to the sum of the array + the missing number.
In other words,
Sum of the AP – Sum of the array = Missing Number.
The advantage of this method is that we can utilize the inbuilt library methods to calculate the sum and minimum number of the array, which will reduce the execution time, especially for languages like Python3 and JavaScript.
Implementation:
C++
// CPP program to find missing // number in a range. #include <bits/stdc++.h> using namespace std; // Function to find the missing number // in a range int missingNum( int arr[], int n) { // calculating the minimum of the array int & minNum = *min_element(arr, arr + n); // calculating the sum of the array int arrSum = 0; arrSum = accumulate(arr, arr + n, arrSum); // calculating the sum of the range [min, min + n] // given using the AP series sum formula // (n + 1) * (2 * min + 1) / 2 int rangeSum = (minNum + minNum + n) * (n + 1) / 2; // the difference between the sum of range // and the sum of array is the missing element return rangeSum - arrSum; } // Driver code int main() { int arr[] = { 13, 12, 11, 15 }; int n = sizeof (arr) / sizeof (arr[0]); // function call cout << missingNum(arr, n); return 0; } // this code is contributed by phasing17 |
Java
// Java program to find missing // number in a range. import java.util.stream.*; class GFG { // Function to find the missing number // in a range static int missingNum( int [] arr, int n) { // calculating the minimum of the array int minNum = IntStream.of(arr).min().getAsInt(); // calculating the sum of the array int arrSum = IntStream.of(arr).sum(); // calculating the sum of the range [min, min + n] // given using the AP series sum formula // (n + 1) * (2 * min + 1) / 2 int rangeSum = (minNum + minNum + n) * (n + 1 ) / 2 ; // the difference between the sum of range // and the sum of array is the missing element return rangeSum - arrSum; } // Driver Code public static void main(String[] args) { int [] arr = { 13 , 12 , 11 , 15 }; int n = arr.length; // function call System.out.println(missingNum(arr, n)); } } //this code is contributed by phasing17 |
Python3
# Python3 program to find missing # number in a range. # Function to find the missing number # in a range def missingNum(arr, n): # calculating the minimum of the array minNum = min (arr) # calculating the sum of the array arrSum = sum (arr) # calculating the sum of the range [min, min + n] # given using the AP series sum formula # (n + 1) * (2 * min + 1) / 2 rangeSum = (minNum + minNum + n) * (n + 1 ) / / 2 # the difference between the sum of range # and the sum of array is the missing element return rangeSum - arrSum # Driver code arr = [ 13 , 12 , 11 , 15 ] n = len (arr) # function call print (missingNum(arr, n)) # this code is contributed by phasing17 |
C#
// C# program to find missing // number in a range. using System; using System.Linq; class GFG { // Function to find the missing number // in a range static int missingNum( int [] arr, int n) { // calculating the minimum of the array int minNum = arr.Min(); // calculating the sum of the array int arrSum = arr.Sum(); // calculating the sum of the range [min, min + n] // given using the AP series sum formula // (n + 1) * (2 * min + 1) / 2 int rangeSum = (minNum + minNum + n) * (n + 1) / 2; // the difference between the sum of range // and the sum of array is the missing element return rangeSum - arrSum; } // Driver Code public static void Main( string [] args) { int [] arr = { 13, 12, 11, 15 }; int n = arr.Length; // function call Console.WriteLine(missingNum(arr, n)); } } // this code is contributed by phasing17 |
Javascript
//JS program to find missing // number in a range. // Function to find the missing number // in a range function missingNum(arr, n) { // calculating the minimum of the array var minNum = Math.min(...arr); // calculating the sum of the array var arrSum = arr.reduce((a, b) => a + b, 0); // calculating the sum of the range [min, min + n] // given using the AP series sum formula // (n + 1) * (2 * min + 1) / 2 var rangeSum = Number((minNum + minNum + n) * (n + 1) / 2); // the difference between the sum of range // and the sum of array is the missing element return rangeSum - arrSum; } // Driver code var arr = [ 13, 12, 11, 15 ]; var n = arr.length; // function call console.log(missingNum(arr, n)); // this code is contributed by phasing17 |
14
Time Complexity: O(n)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!