Given an array arr[] of measurement N-1 with integers within the vary of [1, N], the duty is to search out the lacking quantity from the primary N integers.
Observe: There aren’t any duplicates within the checklist.
Examples:
Enter: arr[] = {1, 2, 4, 6, 3, 7, 8}, N = 8
Output: 5
Clarification: The lacking quantity between 1 to eight is 5
Enter: arr[] = {1, 2, 3, 5}, N = 5
Output: 4
Clarification: The lacking quantity between 1 to five is 4
Method 1 (Utilizing Hashing): The concept behind the next method is
The numbers can be within the vary (1, N), an array of measurement N could be maintained to maintain report of the weather current within the given array
- Create a temp array temp[] of measurement n + 1 with all preliminary values as 0.
- Traverse the enter array arr[], and do following for every arr[i]
- if(temp[arr[i]] == 0) temp[arr[i]] = 1
- Traverse temp[] and output the array factor having worth as 0 (That is the lacking factor).
Under is the implementation of the above method:
C
#embrace <stdio.h>
void findMissing(int arr[], int N)
{
int temp[N + 1];
for (int i = 0; i <= N; i++) {
temp[i] = 0;
}
for (int i = 0; i < N; i++) {
temp[arr[i] - 1] = 1;
}
int ans;
for (int i = 0; i <= N; i++) {
if (temp[i] == 0)
ans = i + 1;
}
printf("%d", ans);
}
int essential()
{
int arr[] = { 1, 3, 7, 5, 6, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
findMissing(arr, n);
}
|
C++
#embrace <bits/stdc++.h>
utilizing namespace std;
void findMissing(int arr[], int N)
{
int i;
int temp[N + 1];
for(int i = 0; i <= N; i++){
temp[i] = 0;
}
for(i = 0; i < N; i++){
temp[arr[i] - 1] = 1;
}
int ans;
for (i = 0; i <= N ; i++) {
if (temp[i] == 0)
ans = i + 1;
}
cout << ans;
}
int essential()
{
int arr[] = { 1, 3, 7, 5, 6, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
findMissing(arr, n);
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
public static void findMissing(int arr[], int N)
{
int i;
int temp[] = new int[N + 1];
for (i = 0; i <= N; i++) {
temp[i] = 0;
}
for (i = 0; i < N; i++) {
temp[arr[i] - 1] = 1;
}
int ans = 0;
for (i = 0; i <= N; i++) {
if (temp[i] == 0)
ans = i + 1;
}
System.out.println(ans);
}
public static void essential(String[] args)
{
int arr[] = { 1, 3, 7, 5, 6, 2 };
int n = arr.size;
findMissing(arr, n);
}
}
|
Python3
def findMissing(arr, N):
temp = [0] * (N+1)
for i in vary(0, N):
temp[arr[i] - 1] = 1
for i in vary(0, N+1):
if(temp[i] == 0):
ans = i + 1
print(ans)
if __name__ == '__main__':
arr = [1, 2, 3, 5]
N = len(arr)
findMissing(arr, N)
|
C#
utilizing System;
public class GFG {
public static void findMissing(int[] arr, int N)
{
int[] temp = new int[N + 1];
for (int i = 0; i < N; i++) {
temp[arr[i] - 1] = 1;
}
int ans = 0;
for (int i = 0; i <= N; i++) {
if (temp[i] == 0)
ans = i + 1;
}
Console.WriteLine(ans);
}
static public void Important()
{
int[] arr = { 1, 3, 7, 5, 6, 2 };
int n = arr.Size;
findMissing(arr, n);
}
}
|
Javascript
<script>
operate findMissing(arr,N){
let i;
let temp = [];
for (i = 0; i <= N; i++) {
temp[i] = 0;
}
for (i = 0; i < N; i++) {
temp[arr[i] - 1] = 1;
}
let ans = 0;
for (i = 0; i <= N; i++) {
if (temp[i] == 0)
ans = i + 1;
}
console.log(ans);
}
let arr = [ 1, 3, 7, 5, 6, 2 ];
let n = arr.size;
findMissing(arr,n);
</script>
|
Time Complexity: O(N)
Auxiliary House: O(N)
Method 2 (Utilizing summation of first N pure numbers): The concept behind the method is to make use of the summation of the primary N numbers.
Discover the sum of the numbers within the vary [1, N] utilizing the formulation N * (N+1)/2. Now discover the sum of all the weather within the array and subtract it from the sum of the primary N pure numbers. This may give the worth of the lacking factor.
Observe the steps talked about under to implement the thought:
- Calculate the sum of the primary N pure numbers as sumtotal= N*(N+1)/2.
- Traverse the array from begin to finish.
- Discover the sum of all of the array components.
- Print the lacking quantity as SumTotal – sum of array
Under is the implementation of the above method:
C
#embrace <stdio.h>
int getMissingNo(int a[], int n)
{
int i, whole;
whole = (n + 1) * (n + 2) / 2;
for (i = 0; i < n; i++)
whole -= a[i];
return whole;
}
void essential()
{
int arr[] = { 1, 2, 3, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
int miss = getMissingNo(arr, N);
printf("%d", miss);
}
|
C++14
#embrace <bits/stdc++.h>
utilizing namespace std;
int getMissingNo(int a[], int n)
{
int N = n + 1;
int whole = (N) * (N + 1) / 2;
for (int i = 0; i < n; i++)
whole -= a[i];
return whole;
}
int essential()
{
int arr[] = { 1, 2, 3, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
int miss = getMissingNo(arr, N);
cout << miss;
return 0;
}
|
Java
import java.util.*;
import java.util.Arrays;
class GFG {
public static int getMissingNo(int[] nums, int n)
{
int sum = ((n + 1) * (n + 2)) / 2;
for (int i = 0; i < n; i++)
sum -= nums[i];
return sum;
}
public static void essential(String[] args)
{
int[] arr = { 1, 2, 3, 5 };
int N = arr.size;
System.out.println(getMissingNo(arr, N));
}
}
|
Python
def getMissingNo(arr, n):
whole = (n + 1)*(n + 2)/2
sum_of_A = sum(arr)
return whole - sum_of_A
if __name__ == '__main__':
arr = [1, 2, 3, 5]
N = len(arr)
miss = getMissingNo(arr, N)
print(miss)
|
C#
utilizing System;
class GFG {
static int getMissingNo(int[] a, int n)
{
int whole = (n + 1) * (n + 2) / 2;
for (int i = 0; i < n; i++)
whole -= a[i];
return whole;
}
public static void Important()
{
int[] arr = { 1, 2, 3, 5 };
int N = 4;
int miss = getMissingNo(arr, N);
Console.Write(miss);
}
}
|
PHP
<?php
operate getMissingNo ($a, $n)
{
$whole = ($n + 1) * ($n + 2) / 2;
for ( $i = 0; $i < $n; $i++)
$whole -= $a[$i];
return $whole;
}
$arr = array(1, 2, 3, 5);
$N = 4;
$miss = getMissingNo($arr, $N);
echo($miss);
?>
|
Javascript
<script>
operate getMissingNo(a, n) {
let whole = Math.ground((n + 1) * (n + 2) / 2);
for (let i = 0; i < n; i++)
whole -= a[i];
return whole;
}
let arr = [ 1, 2, 3, 5 ];
let N = arr.size;
let miss = getMissingNo(arr, N);
doc.write(miss);
</script>
|
Time Complexity: O(N)
Auxiliary House: O(1)
Modification for Overflow: The method stays the identical however there could be an overflow if N is giant.
So as to keep away from integer overflow, choose one quantity from the vary [1, N] and subtract a quantity from the given array (don’t subtract the identical quantity twice). This fashion there gained’t be any integer overflow.
Algorithm:
- Create a variable sum = 1 which is able to retailer the lacking quantity and a counter variable c = 2.
- Traverse the array from begin to finish.
- Replace the worth of sum as sum = sum – array[i] + c and increment c by 1. This performs the duty talked about within the above thought]
- Print the lacking quantity as a sum.
Under is the implementation of the above method:
C
#embrace <stdio.h>
int getMissingNo(int a[], int n)
{
int i, whole = 1;
for (i = 2; i < (n + 1); i++) {
whole += i;
whole -= a[i - 2];
}
return whole;
}
void essential()
{
int arr[] = { 1, 2, 3, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
printf("%d", getMissingNo(arr, N));
}
|
C++14
#embrace <bits/stdc++.h>
utilizing namespace std;
int getMissingNo(int a[], int n)
{
int i, whole = 1;
for (i = 2; i < (n + 1); i++) {
whole += i;
whole -= a[i - 2];
}
return whole;
}
int essential()
{
int arr[] = { 1, 2, 3, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << getMissingNo(arr, N);
return 0;
}
|
Java
class GFG {
static int getMissingNo(int a[], int n)
{
int whole = 1;
for (int i = 2; i < (n + 1); i++) {
whole += i;
whole -= a[i - 2];
}
return whole;
}
public static void essential(String[] args)
{
int[] arr = { 1, 2, 3, 5 };
int N = arr.size;
System.out.println(getMissingNo(arr, N));
}
}
|
Python3
def getMissingNo(a, n):
i, whole = 0, 1
for i in vary(2, n + 2):
whole += i
whole -= a[i - 2]
return whole
if __name__ == '__main__':
arr = [1, 2, 3, 5]
N = len(arr)
print(getMissingNo(arr, N))
|
C#
utilizing System;
class GFG {
static int getMissingNo(int[] a, int n)
{
int i, whole = 1;
for (i = 2; i < (n + 1); i++) {
whole += i;
whole -= a[i - 2];
}
return whole;
}
public static void Important()
{
int[] arr = { 1, 2, 3, 5 };
int N = (arr.Size);
Console.Write(getMissingNo(arr, N));
}
}
|
Javascript
<script>
operate getMissingNo(a, n)
{
let i, whole=1;
for (i = 2; i< (n+1); i++)
{
whole += i;
whole -= a[i-2];
}
return whole;
}
let arr = [1, 2, 3, 5];
let N = arr.size;
doc.write(getMissingNo(arr, N));
</script>
|
Time Complexity: O(N). Just one traversal of the array is required.
Auxiliary House: O(1). No further house is required
Method 3 (Utilizing binary operations): This methodology makes use of the strategy of XOR to unravel the issue.
XOR has sure properties
- Assume a1 ⊕ a2 ⊕ a3 ⊕ . . . ⊕ an = a and a1 ⊕ a2 ⊕ a3 ⊕ . . . ⊕ an-1 = b
- Then a ⊕ b = an
Observe the steps talked about under to implement the thought:
- Create two variables a = 0 and b = 0
- Run a loop from i = 1 to N:
- For each index, replace a as a = a ^ i
- Now traverse the array from i = begin to finish.
- For each index, replace b as b = b ^ arr[i].
- The lacking quantity is a ^ b.
Under is the implementation of the above method:
C
#embrace <stdio.h>
int getMissingNo(int a[], int n)
{
int i;
int x1 = a[0];
int x2 = 1;
for (i = 1; i < n; i++)
x1 = x1 ^ a[i];
for (i = 2; i <= n + 1; i++)
x2 = x2 ^ i;
return (x1 ^ x2);
}
void essential()
{
int arr[] = { 1, 2, 3, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
int miss = getMissingNo(arr, N);
printf("%d", miss);
}
|
C++
#embrace <bits/stdc++.h>
utilizing namespace std;
int getMissingNo(int a[], int n)
{
int x1 = a[0];
int x2 = 1;
for (int i = 1; i < n; i++)
x1 = x1 ^ a[i];
for (int i = 2; i <= n + 1; i++)
x2 = x2 ^ i;
return (x1 ^ x2);
}
int essential()
{
int arr[] = { 1, 2, 3, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
int miss = getMissingNo(arr, N);
cout << miss;
return 0;
}
|
Java
class Important {
static int getMissingNo(int a[], int n)
{
int x1 = a[0];
int x2 = 1;
for (int i = 1; i < n; i++)
x1 = x1 ^ a[i];
for (int i = 2; i <= n + 1; i++)
x2 = x2 ^ i;
return (x1 ^ x2);
}
public static void essential(String args[])
{
int arr[] = { 1, 2, 3, 5 };
int N = arr.size;
int miss = getMissingNo(arr, N);
System.out.println(miss);
}
}
|
Python3
def getMissingNo(a, n):
x1 = a[0]
x2 = 1
for i in vary(1, n):
x1 = x1 ^ a[i]
for i in vary(2, n + 2):
x2 = x2 ^ i
return x1 ^ x2
if __name__ == '__main__':
arr = [1, 2, 3, 5]
N = len(arr)
miss = getMissingNo(arr, N)
print(miss)
|
C#
utilizing System;
class GFG {
static int getMissingNo(int[] a, int n)
{
int x1 = a[0];
int x2 = 1;
for (int i = 1; i < n; i++)
x1 = x1 ^ a[i];
for (int i = 2; i <= n + 1; i++)
x2 = x2 ^ i;
return (x1 ^ x2);
}
public static void Important()
{
int[] arr = { 1, 2, 3, 5 };
int N = 4;
int miss = getMissingNo(arr, N);
Console.Write(miss);
}
}
|
PHP
<?php
operate getMissingNo($a, $n)
{
$x1 = $a[0];
$x2 = 1;
for ($i = 1; $i < $n; $i++)
$x1 = $x1 ^ $a[$i];
for ($i = 2; $i <= $n + 1; $i++)
$x2 = $x2 ^ $i;
return ($x1 ^ $x2);
}
$arr = array(1, 2, 3, 5);
$N = 4;
$miss = getMissingNo($arr, $N);
echo($miss);
?>
|
Javascript
<script>
operate getMissingNo(a, n)
{
var x1 = a[0];
var x2 = 1;
for (var i = 1; i < n; i++) x1 = x1 ^ a[i];
for (var i = 2; i <= n + 1; i++) x2 = x2 ^ i;
return x1 ^ x2;
}
var arr = [1, 2, 3, 5];
var N = arr.size;
var miss = getMissingNo(arr, N);
doc.write(miss);
</script>
|
Time Complexity: O(N)
Auxiliary House: O(1)
Method 4 (Utilizing Cyclic Type): The concept behind it’s as follows:
All of the given array numbers are sorted and within the vary of 1 to n-1. If the vary is 1 to N then the index of each array factor would be the similar as (worth – 1).
Observe the under steps to implement the thought:
- Use cyclic kind to kind the weather in linear time.
- Now traverse from i = 0 to the tip of the array:
- If arr[i] shouldn’t be the identical as i+1 then the lacking factor is (i+1).
- If all components are current then N is the lacking factor within the vary [1, N].
Under is the implementation of the above method.
C
#embrace <stdio.h>
int getMissingNo(int a[], int n)
{
int i = 0;
whereas (i < n) {
int right = a[i] - 1;
if (a[i] < n && a[i] != a[correct]) {
int temp = a[i];
a[i] = a[correct];
a[correct] = temp;
}
else {
i++;
}
}
for (int i = 0; i < n; i++) {
if (i != a[i] - 1) {
return i + 1;
}
}
return n;
}
int essential()
{
int arr[] = { 1, 2, 3, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
int miss = getMissingNo(arr, N);
printf("%d", miss);
return 0;
}
|
C++
#embrace <bits/stdc++.h>
utilizing namespace std;
int getMissingNo(int a[], int n)
{
int i = 0;
whereas (i < n) {
int right = a[i] - 1;
if (a[i] < n && a[i] != a[correct]) {
swap(a[i], a[correct]);
}
else {
i++;
}
}
for (int i = 0; i < n; i++) {
if (i != a[i] - 1) {
return i + 1;
}
}
return n;
}
int essential()
{
int arr[] = { 1, 2, 3, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
int miss = getMissingNo(arr, N);
cout << (miss);
return 0;
}
|
Java
import java.util.*;
public class MissingNumber {
public static void essential(String[] args)
{
int[] arr = { 1, 2, 3, 5 };
int N = arr.size;
int ans = getMissingNo(arr, N);
System.out.println(ans);
}
static int getMissingNo(int[] arr, int n)
{
int i = 0;
whereas (i < n) {
int correctpos = arr[i] - 1;
if (arr[i] < n && arr[i] != arr[correctpos]) {
swap(arr, i, correctpos);
}
else {
i++;
}
}
for (int index = 0; index < arr.size; index++) {
if (arr[index] != index + 1) {
return index + 1;
}
}
return arr.size;
}
static void swap(int[] arr, int i, int correctpos)
{
int temp = arr[i];
arr[i] = arr[correctpos];
arr[correctpos] = temp;
}
}
|
Python3
def getMissingNo(arr, n) :
i = 0;
whereas (i < n) :
correctpos = arr[i] - 1;
if (arr[i] < n and arr[i] != arr[correctpos]) :
arr[i],arr[correctpos] = arr[correctpos], arr[i]
else :
i += 1;
for index in vary(n) :
if (arr[index] != index + 1) :
return index + 1;
return n;
if __name__ == "__main__" :
arr = [ 1, 2, 3, 5 ];
N = len(arr);
print(getMissingNo(arr, N));
|
C#
utilizing System;
class GFG {
static int getMissingNo(int[] arr, int n)
{
int i = 0;
whereas (i < n) {
int correctpos = arr[i] - 1;
if (arr[i] < n && arr[i] != arr[correctpos]) {
swap(arr, i, correctpos);
}
else {
i++;
}
}
for (int index = 0; index < n; index++) {
if (arr[index] != index + 1) {
return index + 1;
}
}
return n;
}
static void swap(int[] arr, int i, int correctpos)
{
int temp = arr[i];
arr[i] = arr[correctpos];
arr[correctpos] = temp;
}
public static void Important()
{
int[] arr = { 1, 2, 4, 5, 6 };
int N = arr.Size;
int ans = getMissingNo(arr, N);
Console.Write(ans);
}
}
|
Javascript
<script>
var arr = [ 1, 2, 3, 5 ];
var N = arr.size;
var ans = getMissingNo(arr, N);
console.log(ans);
operate getMissingNo(arr, n)
{
var i = 0;
whereas (i < n) {
var correctpos = arr[i] - 1;
if (arr[i] < n && arr[i] != arr[correctpos]) {
swap(arr, i, correctpos);
}
else {
i++;
}
}
for (var index = 0; index < arr.size; index++) {
if (arr[index] != index + 1) {
return index + 1;
}
}
return n;
}
operate swap(arr, i, correctpos)
{
var temp = arr[i];
arr[i] = arr[correctpos];
arr[correctpos] = temp;
}
</script>
|
Time Complexity: O(N), requires (N-1) comparisons
Auxiliary Complexity: O(1)
Method 5 (Use components as Index and mark the visited locations as unfavorable): Use the under thought to get the method
Traverse the array. Whereas traversing, use absolutely the worth of each factor as an index and make the worth at this index as unfavorable to mark it visited. To search out lacking, traverse the array once more and search for a constructive worth.
Observe the steps to unravel the issue:
- Traverse the given array
- If absolutely the worth of present factor is bigger than measurement of the array, then proceed.
- else multiply the (absolute worth of (present factor) – 1)th index with -1.
- Initialize a variable ans = measurement + 1.
- Traverse the array and comply with the steps:
- if the worth is constructive assign ans = index + 1
- Print ans because the lacking worth.
Under is the implementation of the above method:
C
#embrace <stdio.h>
#embrace <stdlib.h>
void findMissing(int arr[], int measurement)
{
int i;
for (i = 0; i < measurement; i++) {
if (abs(arr[i]) - 1 == measurement) {
proceed;
}
int ind = abs(arr[i]) - 1;
arr[ind] *= -1;
}
int ans = measurement + 1;
for (i = 0; i < measurement; i++) {
if (arr[i] > 0)
ans = i + 1;
}
printf("%d", ans);
}
int essential()
{
int arr[] = { 1, 3, 7, 5, 6, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
findMissing(arr, n);
return 0;
}
|
C++
#embrace <bits/stdc++.h>
utilizing namespace std;
void findMissing(int arr[], int measurement)
{
int i;
for (i = 0; i < measurement; i++) {
if(abs(arr[i]) - 1 == measurement){
proceed;
}
int ind = abs(arr[i]) - 1;
arr[ind] *= -1;
}
int ans = measurement + 1;
for (i = 0; i < measurement; i++) {
if (arr[i] > 0)
ans = i + 1;
}
cout << ans;
}
int essential()
{
int arr[] = { 1, 3, 7, 5, 6, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
findMissing(arr, n);
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
public static void findMissing(int arr[], int measurement)
{
int i;
for (i = 0; i < measurement; i++) {
if (Math.abs(arr[i]) - 1 == measurement) {
proceed;
}
int ind = Math.abs(arr[i]) - 1;
arr[ind] *= -1;
}
int ans = measurement + 1;
for (i = 0; i < measurement; i++) {
if (arr[i] > 0)
ans = i + 1;
}
System.out.println(ans);
}
public static void essential(String[] args)
{
int arr[] = { 1, 3, 7, 5, 6, 2 };
int n = arr.size;
findMissing(arr, n);
}
}
|
Python3
def findMissing(a, measurement):
for i in vary(0, n):
if (abs(arr[i]) - 1 == measurement):
proceed
ind = abs(arr[i]) - 1
arr[ind] *= -1
ans = measurement + 1
for i in vary(0, n):
if (arr[i] > 0):
ans = i + 1
print(ans)
if __name__ == '__main__':
arr = [1, 3, 7, 5, 6, 2]
n = len(arr)
findMissing(arr, n)
|
C#
utilizing System;
public class GFG {
public static void findMissing(int[] arr, int measurement)
{
for (int i = 0; i < measurement; i++) {
if (Math.Abs(arr[i]) - 1 == measurement)
proceed;
int ind = Math.Abs(arr[i]) - 1;
arr[ind] *= -1;
}
int ans = measurement + 1;
for (int i = 0; i < measurement; i++) {
if (arr[i] > 0)
ans = i + 1;
}
Console.WriteLine(ans);
}
static public void Important()
{
int[] arr = { 1, 3, 7, 5, 6, 2 };
int n = arr.Size;
findMissing(arr, n);
}
}
|
Javascript
<script>
operate findMissing(arr,measurement){
let i;
for (i = 0; i < measurement; i++) {
if (Math.abs(arr[i]) - 1 == measurement) {
proceed;
}
let ind = Math.abs(arr[i]) - 1;
arr[ind] *= -1;
}
let ans = measurement + 1;
for (i = 0; i < measurement; i++) {
if (arr[i] > 0)
ans = i + 1;
}
console.log(ans);
}
let arr = [ 1, 3, 7, 5, 6, 2 ];
let n = arr.size;
findMissing(arr,n);
</script>
|
Time Complexity: O(N)
Auxiliary House: O(1)
