Skip to main content

Missing Number

Problem​

Ritu has all numbers from 1 to n in an array arr of length n-1 except one number. You have to find which number, Ritu doesn't have from 1 to n.

NOTE: Don't use Sorting

Examples:​

Example 1:

Input:
n = 4
arr = {1, 4, 3}
Output: 2
Explanation:
Ritu doesn't have number 2

Example 2:

Input:                        
n = 5
arr = {2, 5, 3, 1}
Output: 4
Explanation:
Ritu doesn't have number 4 in her collection

Your task:​

You don't need to read input or print anything. Your task is to complete the function missingNumber() which takes an integer n and an array arr of length n-1 as inputs and returns the missing number.

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

Constraints:​

  • 2≤n≤1042 ≤ n ≤ 10^4
  • 1≤arr[i]≤n1 ≤ arr[i] ≤ n
  • Size(arr)=n−1Size(arr) = n-1

Solution​

Python​

def missingNumber(self, n : int, arr : List[int]) -> int:
total_sum = n * (n + 1) // 2
array_sum = sum(arr)
return total_sum - array_sum

Java​

public static int missingNumber(int n, int[] arr) {
int total_sum = n * (n + 1) / 2;
int array_sum = 0;
for(int i = 0; i<arr.length; i++)
array_sum+=arr[i];
int result = total_sum - array_sum;
return result;
}

C++​

int missingNumber(int n, vector<int> &arr) {
int total_sum = n * (n + 1) / 2;
int array_sum = 0;
for (int i = 0; i < arr.size(); i++) {
array_sum += arr[i];
}
int result = total_sum - array_sum;
return result;
}

C​

int missingNumber(int n, int arr[], int size) {
int total_sum = n * (n + 1) / 2;
int array_sum = 0;
for (int i = 0; i < size; i++) {
array_sum += arr[i];
}
int result = total_sum - array_sum;
return result;
}
  • Time Complexity: O(n)O(n)
  • Auxiliary Space: O(1)O(1)