Posted on by Kalkicode
Code Array

# Find a missing number in an array

The problem is to finding a missing number in an array. Given an array containing a sequence of unique numbers, with one number missing, our goal is to identify that missing number. This type of problem arises in various scenarios, such as data validation, error detection, and cryptographic applications.

## Problem Statement

Given an array of unique numbers, one number is missing from the sequence. We need to find and output the missing number.

## Example

Let's consider a few examples:

1. `arr1 = [1, 3, 4, 5, 6]` → Missing number: 2
2. `arr2 = [1, 2, 3, 4, 5, 6, 7, 9]` → Missing number: 8
3. `arr3 = [-7, -6, -4, -3, -2, -1]` → Missing number: -5
4. `arr4 = [1, 6, 5, 4, 2]` → Missing number: 3

## Idea to Solve

1. Calculate the expected sum of the sequence with the missing number using the formula `(n * (n + 1)) / 2`, where `n` is the size of the array plus one.
2. Calculate the actual sum of the elements in the array.
3. Subtract the actual sum from the expected sum to find the missing number.

## Pseudocode

``````function missing_element(arr, size):
if size <= 0:
return

calculate expected_sum = (size + 1) * (size + 2) / 2

if arr[0] < 0:
set expected_sum = -expected_sum

actual_sum = 0
for i from 0 to size - 1:
actual_sum = actual_sum + arr[i]

missing_number = expected_sum - actual_sum
print "Missing element:", missing_number

arr1 = [1, 3, 4, 5, 6]
size1 = length of arr1
missing_element(arr1, size1)

arr2 = [1, 2, 3, 4, 5, 6, 7, 9]
size2 = length of arr2
missing_element(arr2, size2)

arr3 = [-7, -6, -4, -3, -2, -1]
size3 = length of arr3
missing_element(arr3, size3)

arr4 = [1, 6, 5, 4, 2]
size4 = length of arr4
missing_element(arr4, size4)``````

## Algorithm Explanation

1. The `missing_element` function calculates the missing number:
• It first checks if the size is non-positive; if so, it returns.
• It calculates the expected sum using the formula based on the array size.
• If the first element is negative, it updates the expected sum to account for negative numbers.
• It calculates the actual sum of the elements in the array.
• The missing number is then computed by subtracting the actual sum from the expected sum.

## Code Solution

``````//C Program
//Find a missing number in an array
#include <stdio.h>

//Find  missing element of given array
void missing_element(int arr[], int size)
{
if (size <= 0)
{
return;
}
// Assume that
// 1) Array are containing all unique element (no have repeat element)
// 2) Array contains element between [ 1 to n ] or [-1 to -n] elements
// 3) Only one element is missing in array
// 4) Array is form of sorted or unsorted
//Calculate sum of all elements in array
int sum = ((size + 1) *(size + 2)) / 2;
if (arr[0] < 0)
{
//When given array contains negative elements
sum = -sum;
}
//loop which is iterating array elements
for (int i = 0; i < size; ++i)
{
//Total sum of array elements are minius by current array element [i].
sum = sum - arr[i];
}
//Display result of missing element
printf("\n Missing element : %d", sum);
}
int main()
{
//Define collection of array elements
int arr1[] = {
1 , 3 , 4 , 5 , 6
};
//Get the size of array
int size = sizeof(arr1) / sizeof(arr1[0]);
missing_element(arr1, size);
int arr2[] = {
1 , 2 , 3 , 4 , 5 , 6 , 7 , 9
};
size = sizeof(arr2) / sizeof(arr2[0]);
missing_element(arr2, size);
//Given array element for (-1 to -n elements)
int arr3[] = {
-7 , -6 , -4 , -3 , -2 , -1
};
size = sizeof(arr3) / sizeof(arr3[0]);
missing_element(arr3, size);
//When given array sequence are unsort.
int arr4[] = {
1 , 6 , 5 , 4 , 2
};
size = sizeof(arr4) / sizeof(arr4[0]);
missing_element(arr4, size);
return 0;
}``````

#### Output

`````` Missing element : 2
Missing element : 8
Missing element : -5
Missing element : 3``````
``````// Java Program
// Find a missing number in an array
class MyArray
{
//Find  missing element of given array
public void missing_element(int[] arr, int size)
{
if (size <= 0)
{
return;
}
// Assume that
// 1) Array are containing all unique element (no have repeat element)
// 2) Array contains element between [ 1 to n ] or [-1 to -n] elements
// 3) Only one element is missing in array
// 4) Array is form of sorted or unsorted
//Calculate sum of all elements in array
int sum = ((size + 1) *(size + 2)) / 2;
if (arr[0] < 0)
{
//When given array contains negative elements
sum = -sum;
}
//loop which is iterating array elements
for (int i = 0; i < size; ++i)
{
//Total sum of array elements are minius by current array element [i].
sum = sum - arr[i];
}
System.out.print("\n Missing element : " + sum);
}
public static void main(String[] args)
{
MyArray obj = new MyArray();
//Define collection of array elements
int[] arr1 = {
1 , 3 , 4 , 5 , 6
};
//Get the size of array
int size = arr1.length;
obj.missing_element(arr1, size);
int[] arr2 = {
1 , 2 , 3 , 4 , 5 , 6 , 7 , 9
};
size = arr2.length;
obj.missing_element(arr2, size);
//Given array element for (-1 to -n elements)
int[] arr3 = {
-7 , -6 , -4 , -3 , -2 , -1
};
size = arr3.length;
obj.missing_element(arr3, size);
//When given array sequence are unsort.
int[] arr4 = {
1 , 6 , 5 , 4 , 2
};
size = arr4.length;
obj.missing_element(arr4, size);
}
}``````

#### Output

`````` Missing element : 2
Missing element : 8
Missing element : -5
Missing element : 3``````
``````//Include header file
#include <iostream>

using namespace std;
// C++ Program
// Find a missing number in an array
class MyArray
{
public:
//Find  missing element of given array
void missing_element(int arr[], int size)
{
if (size <= 0)
{
return;
}
// Assume that
// 1) Array are containing all unique element (no have repeat element)
// 2) Array contains element between [ 1 to n ] or [-1 to -n] elements
// 3) Only one element is missing in array
// 4) Array is form of sorted or unsorted
//Calculate sum of all elements in array
int sum = ((size + 1) * (size + 2)) / 2;
if (arr[0] < 0)
{
//When given array contains negative elements
sum = -sum;
}
//loop which is iterating array elements
for (int i = 0; i < size; ++i)
{
//Total sum of array elements are minius by current array element [i].
sum = sum - arr[i];
}
cout << "\n Missing element : " << sum;
}
};
int main()
{
MyArray obj = MyArray();
int arr1[] = {
1 , 3 , 4 , 5 , 6
};
//Get the size of array
int size = sizeof(arr1) / sizeof(arr1[0]);
obj.missing_element(arr1, size);
int arr2[] = {
1 , 2 , 3 , 4 , 5 , 6 , 7 , 9
};
size = sizeof(arr2) / sizeof(arr2[0]);
obj.missing_element(arr2, size);
int arr3[] = {
-7 , -6 , -4 , -3 , -2 , -1
};
size = sizeof(arr3) / sizeof(arr3[0]);
obj.missing_element(arr3, size);
int arr4[] = {
1 , 6 , 5 , 4 , 2
};
size = sizeof(arr4) / sizeof(arr4[0]);
obj.missing_element(arr4, size);
return 0;
}``````

#### Output

`````` Missing element : 2
Missing element : 8
Missing element : -5
Missing element : 3``````
``````//Include namespace system
using System;
// C# Program
// Find a missing number in an array
class MyArray
{
//Find  missing element of given array
public void missing_element(int[] arr, int size)
{
if (size <= 0)
{
return;
}
// Assume that
// 1) Array are containing all unique element (no have repeat element)
// 2) Array contains element between [ 1 to n ] or [-1 to -n] elements
// 3) Only one element is missing in array
// 4) Array is form of sorted or unsorted
//Calculate sum of all elements in array
int sum = ((size + 1) * (size + 2)) / 2;
if (arr[0] < 0)
{
//When given array contains negative elements
sum = -sum;
}
//loop which is iterating array elements
for (int i = 0; i < size; ++i)
{
//Total sum of array elements are minius by current array element [i].
sum = sum - arr[i];
}
Console.Write("\n Missing element : " + sum);
}
public static void Main(String[] args)
{
MyArray obj = new MyArray();
int[] arr1 = {
1 , 3 , 4 , 5 , 6
};
//Get the size of array
int size = arr1.Length;
obj.missing_element(arr1, size);
int[] arr2 = {
1 , 2 , 3 , 4 , 5 , 6 , 7 , 9
};
size = arr2.Length;
obj.missing_element(arr2, size);
int[] arr3 = {
-7 , -6 , -4 , -3 , -2 , -1
};
size = arr3.Length;
obj.missing_element(arr3, size);
int[] arr4 = {
1 , 6 , 5 , 4 , 2
};
size = arr4.Length;
obj.missing_element(arr4, size);
}
}``````

#### Output

`````` Missing element : 2
Missing element : 8
Missing element : -5
Missing element : 3``````
``````<?php
// Php Program
// Find a missing number in an array
class MyArray
{
//Find  missing element of given array
public	function missing_element( & \$arr, \$size)
{
if (\$size <= 0)
{
return;
}
// Assume that
// 1) Array are containing all unique element (no have repeat element)
// 2) Array contains element between [ 1 to n ] or [-1 to -n] elements
// 3) Only one element is missing in array
// 4) Array is form of sorted or unsorted
//Calculate sum of all elements in array
\$sum = intval(((\$size + 1) * (\$size + 2)) / 2);
if (\$arr[0] < 0)
{
//When given array contains negative elements
\$sum = -\$sum;
}
//loop which is iterating array elements
for (\$i = 0; \$i < \$size; ++\$i)
{
//Total sum of array elements are minius by current array element [i].
\$sum = \$sum - \$arr[\$i];
}
echo "\n Missing element : ". \$sum;
}
}

function main()
{
\$obj = new MyArray();
//Define collection of array elements
\$arr1 = array(1, 3, 4, 5, 6);
//Get the size of array
\$size = count(\$arr1);
\$obj->missing_element(\$arr1, \$size);
\$arr2 = array(1, 2, 3, 4, 5, 6, 7, 9);
\$size = count(\$arr2);
\$obj->missing_element(\$arr2, \$size);
//Given array element for (-1 to -n elements)
\$arr3 = array(-7, -6, -4, -3, -2, -1);
\$size = count(\$arr3);
\$obj->missing_element(\$arr3, \$size);
//When given array sequence are unsort.
\$arr4 = array(1, 6, 5, 4, 2);
\$size = count(\$arr4);
\$obj->missing_element(\$arr4, \$size);
}
main();``````

#### Output

`````` Missing element : 2
Missing element : 8
Missing element : -5
Missing element : 3``````
``````// Node Js Program
// Find a missing number in an array
class MyArray
{
//Find  missing element of given array
missing_element(arr, size)
{
if (size <= 0)
{
return;
}
// Assume that
// 1) Array are containing all unique element (no have repeat element)
// 2) Array contains element between [ 1 to n ] or [-1 to -n] elements
// 3) Only one element is missing in array
// 4) Array is form of sorted or unsorted
//Calculate sum of all elements in array
var sum = parseInt(((size + 1) * (size + 2)) / 2);
if (arr[0] < 0)
{
//When given array contains negative elements
sum = -sum;
}
//loop which is iterating array elements
for (var i = 0; i < size; ++i)
{
//Total sum of array elements are minius by current array element [i].
sum = sum - arr[i];
}
process.stdout.write("\n Missing element : " + sum);
}
}

function main()
{
var obj = new MyArray();
//Define collection of array elements
var arr1 = [1, 3, 4, 5, 6];
//Get the size of array
var size = arr1.length;
obj.missing_element(arr1, size);
var arr2 = [1, 2, 3, 4, 5, 6, 7, 9];
size = arr2.length;
obj.missing_element(arr2, size);
//Given array element for (-1 to -n elements)
var arr3 = [-7, -6, -4, -3, -2, -1];
size = arr3.length;
obj.missing_element(arr3, size);
//When given array sequence are unsort.
var arr4 = [1, 6, 5, 4, 2];
size = arr4.length;
obj.missing_element(arr4, size);
}
main();``````

#### Output

`````` Missing element : 2
Missing element : 8
Missing element : -5
Missing element : 3``````
``````#  Python 3 Program
#  Find a missing number in an array
class MyArray :
# Find  missing element of given array
def missing_element(self, arr, size) :
if (size <= 0) :
return

#  Assume that
#  1) Array are containing all unique element (no have repeat element)
#  2) Array contains element between [ 1 to n ] or [-1 to -n] elements
#  3) Only one element is missing in array
#  4) Array is form of sorted or unsorted
# Calculate sum of all elements in array
sum = int(((size + 1) * (size + 2)) / 2)
if (arr[0] < 0) :
# When given array contains negative elements
sum = -sum

i = 0
# loop which is iterating array elements
while (i < size) :
# Total sum of array elements are minius by current array element [i].
sum = sum - arr[i]
i += 1

print("\n Missing element : ", sum, end = "")

def main() :
obj = MyArray()
# Define collection of array elements
arr1 = [1, 3, 4, 5, 6]
# Get the size of array
size = len(arr1)
obj.missing_element(arr1, size)
arr2 = [1, 2, 3, 4, 5, 6, 7, 9]
size = len(arr2)
obj.missing_element(arr2, size)
# Given array element for (-1 to -n elements)
arr3 = [-7, -6, -4, -3, -2, -1]
size = len(arr3)
obj.missing_element(arr3, size)
# When given array sequence are unsort.
arr4 = [1, 6, 5, 4, 2]
size = len(arr4)
obj.missing_element(arr4, size)

if __name__ == "__main__": main()``````

#### Output

`````` Missing element :  2
Missing element :  8
Missing element :  -5
Missing element :  3``````
``````#  Ruby Program
#  Find a missing number in an array
class MyArray

# Find  missing element of given array
def missing_element(arr, size)

if (size <= 0)

return
end
#  Assume that
#  1) Array are containing all unique element (no have repeat element)
#  2) Array contains element between [ 1 to n ] or [-1 to -n] elements
#  3) Only one element is missing in array
#  4) Array is form of sorted or unsorted
# Calculate sum of all elements in array
sum = ((size + 1) * (size + 2)) / 2
if (arr[0] < 0)

# When given array contains negative elements
sum = -sum
end
i = 0
# loop which is iterating array elements
while (i < size)

# Total sum of array elements are minius by current array element [i].
sum = sum - arr[i]
i += 1
end
print("\n Missing element : ", sum)
end
end
def main()

obj = MyArray.new()
# Define collection of array elements
arr1 = [1, 3, 4, 5, 6]
# Get the size of array
size = arr1.length
obj.missing_element(arr1, size)
arr2 = [1, 2, 3, 4, 5, 6, 7, 9]
size = arr2.length
obj.missing_element(arr2, size)
# Given array element for (-1 to -n elements)
arr3 = [-7, -6, -4, -3, -2, -1]
size = arr3.length
obj.missing_element(arr3, size)
# When given array sequence are unsort.
arr4 = [1, 6, 5, 4, 2]
size = arr4.length
obj.missing_element(arr4, size)
end
main()``````

#### Output

`````` Missing element : 2
Missing element : 8
Missing element : -5
Missing element : 3``````
``````// Scala Program
// Find a missing number in an array
class MyArray
{
//Find  missing element of given array
def missing_element(arr: Array[Int], size: Int): Unit = {
if (size <= 0)
{
return;
}
// Assume that
// 1) Array are containing all unique element (no have repeat element)
// 2) Array contains element between [ 1 to n ] or [-1 to -n] elements
// 3) Only one element is missing in array
// 4) Array is form of sorted or unsorted
//Calculate sum of all elements in array
var sum: Int = (((size + 1) * (size + 2)) / 2).toInt;
if (arr(0) < 0)
{
//When given array contains negative elements
sum = -sum;
}
var i: Int = 0;
//loop which is iterating array elements
while (i < size)
{
//Total sum of array elements are minius by current array element [i].
sum = sum - arr(i);
i += 1;
}
print("\n Missing element : " + sum);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
//Define collection of array elements
var arr1: Array[Int] = Array(1, 3, 4, 5, 6);
//Get the size of array
var size: Int = arr1.length;
obj.missing_element(arr1, size);
var arr2: Array[Int] = Array(1, 2, 3, 4, 5, 6, 7, 9);
size = arr2.length;
obj.missing_element(arr2, size);
//Given array element for (-1 to -n elements)
var arr3: Array[Int] = Array(-7, -6, -4, -3, -2, -1);
size = arr3.length;
obj.missing_element(arr3, size);
//When given array sequence are unsort.
var arr4: Array[Int] = Array(1, 6, 5, 4, 2);
size = arr4.length;
obj.missing_element(arr4, size);
}
}``````

#### Output

`````` Missing element : 2
Missing element : 8
Missing element : -5
Missing element : 3``````
``````// Swift Program
// Find a missing number in an array
class MyArray
{
//Find  missing element of given array
func missing_element(_ arr: [Int], _ size: Int)
{
if (size <= 0)
{
return;
}
// Assume that
// 1) Array are containing all unique element (no have repeat element)
// 2) Array contains element between [ 1 to n ] or [-1 to -n] elements
// 3) Only one element is missing in array
// 4) Array is form of sorted or unsorted
//Calculate sum of all elements in array
var sum: Int = ((size + 1) * (size + 2)) / 2;
if (arr[0] < 0)
{
//When given array contains negative elements
sum = -sum;
}
var i: Int = 0;
//loop which is iterating array elements
while (i < size)
{
//Total sum of array elements are minius by current array element [i].
sum = sum - arr[i];
i += 1;
}
print("\n Missing element : ", sum, terminator: "");
}
}
func main()
{
let obj: MyArray = MyArray();
//Define collection of array elements
let arr1: [Int] = [1, 3, 4, 5, 6];
//Get the size of array
var size: Int = arr1.count;
obj.missing_element(arr1, size);
let arr2: [Int] = [1, 2, 3, 4, 5, 6, 7, 9];
size = arr2.count;
obj.missing_element(arr2, size);
//Given array element for (-1 to -n elements)
let arr3: [Int] = [-7, -6, -4, -3, -2, -1];
size = arr3.count;
obj.missing_element(arr3, size);
//When given array sequence are unsort.
let arr4: [Int] = [1, 6, 5, 4, 2];
size = arr4.count;
obj.missing_element(arr4, size);
}
main();``````

#### Output

`````` Missing element :  2
Missing element :  8
Missing element :  -5
Missing element :  3``````

## Time Complexity

The time complexity of this algorithm is O(n), where n is the number of elements in the array. This is because there's a loop that iterates through the array once to calculate the actual sum of the elements. Other calculations are constant time operations.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post