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.

New Comment