# Problem Statement
You are given an array of positive numbers from $1$ to $n$, such that all numbers from $1$ to $n$ are present except one number, $x$. You have to find $x$. The input array is not sorted.

For example, let's look at the below array.

# Hint
* How would you calculate the sum of numbers from $1$ to $n$?

<br>

# Try it yourself

#include <iostream>
#include <vector>

using namespace std;

int FindMissing(const vector<int>& input) {
	//TODO: Write - Your - Code
	return -1;
}

// #include <iostream>
// #include <numeric>
// #include <vector>
// #include <time.h>
// #include <stdlib.h>

// using namespace std;


// void print(vector<int>& v) {
//   cout << "vector = {";
//   for (int x : v) {
//     cout << x << ",";
//   }
//   cout << "}" << endl;
// }

// template <class T>
// void print_list(vector<T>& v) {
//   cout << "{ ";
//   for (auto x : v) {
//     cout << x << ",";
//   }
//   cout << "}" << endl;
// }

// template <class T>
// bool is_equal(vector<T>& v1, vector<T>& v2) {
//   if (v1.size() != v2.size()) {
//     return false;
//   }

//   int idx = 0;
//   for (auto x : v1) {
//     if (x != v2[idx]) {
//       return false;
//     }
//     ++idx;
//   }

//   return true;
// }

// template<typename T>
// vector<T> create_random_vector(int length, T max_value = 100) {
//   vector<T> v(length);
//   srand (time(nullptr));
//   for(T i = 0; i < length; ++i) {
//     v[i] = static_cast<T>(rand() % max_value);
//   }
//   return v;
// }

// vector<int> create_random_vector(int length, int max_value = 100) {
//   vector<int> v(length);
//   srand (time(nullptr));
//   for(int i = 0; i < length; ++i) {
//     v[i] = rand() % max_value;
//   }
//   return v;
// }

// int find_in_vector(vector<int>& v, int k) {
//   for (int i = 0; i < v.size(); ++i) {
//     if (k == v[i]) {
//       return i;
//     }
//   }
//   return -1;
// }

// bool is_sorted(vector<int> v) {

//   for (int i = 1; i < v.size(); ++i) {
//     if (v[i] < v[i-1]) {
//       return false;
//     }
//   }

//   return true;
// }

// Importing required functions
import java.util.*;

class FindMissing {
	static int findMissing(List<Integer> input) {
		// TODO: Write - Your - Code
		return -1;
	}
}


Java

def find_missing(input):
  #TODO: Write - Your - Code
  return -1

Python

let findMissing = function(input) {
  //TODO: Write - Your - Code
  return -1;
};

JavaScript

def find_missing(input)
  #TODO: Write - Your - Code
  return -1
end

Ruby

package main
import (
	"fmt"
	"encoding/json"
)

func FindMissing(input []int) int {

	return -1
}

#include <iostream>
#include <vector>
#include <string>
#include <numeric>

using namespace std;

int FindMissing(const vector<int>& input) {
	// Calculate sum of all elements in the input vector
	// The accumulate function can this for us
	int actual_sum = accumulate(input.begin(), input.end(), 0);
	int n = input.size();

	// Find the sum of first n numbers using the arithmetic series sum formula,
	// i.e.,​ ​(n∗(n+1))/2
	int sum_of_n = (n * (n + 1)) / 2;

	// The difference between sum_of_n and actual_sum, is the missing number in the
	// array
	return sum_of_n - actual_sum;
}

int main() {
	vector<vector<int> > vec_list = {{0}, {3, 7, 1, 2, 0, 4, 5}, {9, 6, 4, 2, 3, 5, 7, 0, 1}};
	for (int i = 0; i < vec_list.size(); i++) {
		cout << i + 1 << ". Original ";
		// A custom function to print the vector
		PrintList(vec_list[i]);
		int missing = FindMissing(vec_list[i]);
		cout << "   The missing number is: " << missing << endl;
		cout << "\n------------------------------------------------------------------------------------------------------\n" << endl;
	}
}

// Importing required functions
import java.util.*;

class FindMissing {
	static int findMissing(List<Integer> input) {
		// calculate sum of all integers
		// in input list
		int actualSum = 0;
		for (Integer x : input) {
			actualSum += x;
		}
		int n = input.size();

		// find the sum of first n numbers using the arithmetic series sum formula,
		// i.e.,​ ​(n∗(n+1))/2
		int sumOfN = (n * (n + 1)) / 2;

		// The difference between sumOfN - actualSum, is the missing number in the array
		return sumOfN - actualSum;
	}

	public static void main(String[] args) {
		Integer[][] vLst = {{0}, {3, 7, 1, 2, 0, 4, 5}, {9, 6, 4, 2, 3, 5, 7, 0, 1}};
		for (int i = 0; i < vLst.length; i++) {
			List<Integer> v = Arrays.asList(vLst[i]);
			System.out.println((i + 1) + ". Original: " + v);
			int missingNumber = findMissing(v);
			System.out.println("   The missing number is: " + missingNumber);
			System.out.println(
					"\n-----------------------------------------------------------------------------------------------------\n");
		}
	}
}


def find_missing(input):
    # calculate sum of all elements 
    # in input list
    actual_sum = sum(input)

    # find the sum of first n numbers using the arithmetic series sum formula, 
    # i.e.,​ ​(n∗(n+1))/2
    n = len(input)
    sum_of_elements = (n * ( n + 1 ) ) / 2
    
    # The difference between sum_of_elements - actual_sum, is the missing number in the array
    return int(sum_of_elements - actual_sum)

# Driver code
def main():
    v_list = [[0], [3,7,1,2,0,4,5], [9,6,4,2,3,5,7,0,1]]
    
    for i in range(len(v_list)):
        print("1. Original:", v_list[i])
        missing_number = find_missing(v_list[i])
        print("   The missing number is: " + str(missing_number))
        print("-" * 100)
    
if __name__ == '__main__':
    main()

let findMissing = function(input) {
    
    //  calculate sum of all integers
    //  in input list
    let actualSum = 0;
    for (let i in input) {
        actualSum += input[i];
    }
    let n = input.length;

    //find the sum of first n numbers using the arithmetic series sum formula, 
    // i.e.,​ ​(n∗(n+1))/2
    let sumOfN =(n * (n + 1)) / 2;

    // The difference between sumOfN - actualSum, is the missing number in the array
    return sumOfN - actualSum;
};

let v = [0];
console.log("1. Original: " + printArray(v));
let missingNumber = findMissing(v);
console.log("   The missing number is: " + missingNumber);
console.log("\n-----------------------------------------------------------------------------------------------------\n" );
let v1 = [3,7,1,2,0,4,5];
console.log("2. Original: " + printArray(v1));
let missingNumber1 = findMissing(v1);
console.log("   The missing number is: " + missingNumber1);
console.log("\n-----------------------------------------------------------------------------------------------------\n" );
let v2 = [9,6,4,2,3,5,7,0,1];
console.log("3. Original: " + printArray(v2));
let missingNumber2 = findMissing(v2);
console.log("   The missing number is: " + missingNumber2);
console.log("\n-----------------------------------------------------------------------------------------------------\n" );

def find_missing(input)
  # calculate sum of all elements 
  # in input list
  actual_sum = input.inject(:+)

  # find the sum of first n numbers using the arithmetic series sum formula, 
  # i.e.,​ ​(n∗(n+1))/2
  n = input.length
  sum_of_elements = ((n * ( n + 1 ) ) / 2).floor
  
  # The difference between sum_of_elements - actual_sum, is the missing number in the array
  return sum_of_elements - actual_sum
end

v = [[0], [3,7,1,2,0,4,5], [9,6,4,2,3,5,7,0,1]]

v.length.times do |i|
  puts (i + 1).to_s + ". Original: " + v[i].to_s
  missing_number = find_missing(v[i])
  puts "   The missing number is: " + missing_number.to_s
  print "-----------------------------------------------------------------------------------------------------\n"
end

package main

import (
	"fmt"
	"strconv"
)
// FindMissing function will find the missing number in an inpur array
func FindMissing(input []int) int {

	/*  calculate sum of all integers
        in input list */
	actualSum := 0

	for  _, inp := range input {
        actualSum += inp
    }


	n := len(input)
	/* find the sum of first n numbers using the arithmetic series sum formula, 
     i.e.,​ ​(n∗(n+1))/2 */
	sumOfN := float64(n * (n + 1)) / float64(2)
	
	// The difference between sumOfN - actualSum, is the missing number in the array
	return int(sumOfN - float64(actualSum))
}

/* ArrayToString is used to convert an integer array to string. 
ArrayToString is used as an helper function in a main function for 
printing purposes. */
func ArrayToString(nums []int) string{
	if len(nums) == 0 {
		return "[]"
	}
	res := "["
	for _, num := range nums {
		res += strconv.Itoa(num) + ", "
	}
	res += "]"
	return res[:len(res) - 3] + "]"
}

func main() {
	array := [][]int{
		{0},
		{3, 7, 1, 2, 0, 4, 5},
		{9, 6, 4, 2, 3, 5, 7, 0, 1},
	}
	for i, arr := range array{
		fmt.Printf("%d.     Original: %s\n", i + 1, ArrayToString(arr))
		missingNumber := FindMissing(arr)
		fmt.Printf("       The missing number is: %d\n", missingNumber)
		fmt.Print("-----------------------------------------------------------------------------------------------------\n")
	}
}


# Solution Explanation

## Runtime Complexity
Linear, $O(n)$.

## Memory Complexity
Constant, $O(1)$.

<br>

## Solution Breakdown

A naive solution is to simply search for every integer between 1 and n in the input array, stopping the search as soon as there is a missing number. Since the input array is not sorted, its time complexity will be $O(n^{2}$).

Can you do better than $O(n^{2}$)? Yes.

You could sort the array and then do a linear scan $O(n$) where you compare all consecutive elements to find the missing number. However, the time complexity of this algorithm is $O(n log n$) due to the time spent in sorting.

You can do better. Here is a linear, $O(n$), solution that uses the arithmetic series sum formula.

$$\sum_{1}^n = \frac{n (n + 1)}{2}$$

​​Here are the steps to find the missing number.
1) Find the sum of elements of all the numbers in the array. Let's call it `sum`. This would require a linear scan, $O(n)$.
2) Then find the expected sum of the first $n$ numbers using the formula: $\frac{(n(n+ 1))}{2}$. Let's call it `total`.
3) The difference between `total` and `sum` is the missing number in the array.




> Practice problems like this and many more by checking out our [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) course!

Given an array of positive numbers from 1 to n, such that all numbers from 1 to n are present except one; find the missing number.

Find the Missing Number

Problem Statement

Hint

Try it yourself

Solution

Solution Explanation

Runtime Complexity

Memory Complexity

Solution Breakdown