content: package math;
  
  import java.util.ArrayList;
  import java.util.List;
  import java.util.Random;
  
  public class FindMissingNumber {
  
      /*
       * 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.
       *
       * Runtime Complexity:
       * Linear, O(n)
       *
       * Memory Complexity:
       * Constant, O(1)
       *
       * Step 1: Find sum 'sum_of_elements' of all the numbers in the array. This would require a linear scan, O(n).
       * Step 2: Then find sum 'expected_sum' of first 'n' numbers using arithmetic series sum formula i.e. ( n * (n + 1) ) / 2.
       * Step 3: Difference between these i.e. 'expected_sum - sum_of_elements' is the missing number in the array.
       *
       * */
  
      protected static int findMissing(List<Integer> input) {
  
          int sum_of_elements = 0;
          for (Integer x : input) {
              sum_of_elements += x;
          }
  
          // There is exactly 1 number missing
          int n = input.size() + 1;
          int actual_sum = (n * (n + 1)) / 2;
          return actual_sum - sum_of_elements;
      }
  
  
      public static void main(String[] args) {
          int n = 5;
          int missingElement = (new Random()).nextInt(n) + 1;
  
          List<Integer> v = new ArrayList<>();
          for (int i = 1; i <= n; ++i) {
              if (i != missingElement)
                  v.add(i);
          }
  
          int actual_missing = findMissing(v);
          System.out.print("Expected Missing = ");
          System.out.print(missingElement);
          System.out.print(" Actual Missing = ");
          System.out.println(actual_missing);
          System.out.println("Missing Element == Actual Missing : " + (missingElement == actual_missing));
      }
  }
  