Find the Missing

CONCEPTS USED:

Basic Mathematics

DIFFICULTY LEVEL:

Medium

PROBLEM STATEMENT(SIMPLIFIED):

Given an array A with N-1 elements, with elements from 1 to N present into it.
Find a single missing element.

Note - Do not use sorting or any in-built function to solve the question.

See original problem statement here

For Example:

Input : A[] = [1, 2, 5, 4, 6, 7]

Output : 3

Explanation : Since 3 is the only element not present in the array.

SOLVING APPROACH:

  1. Given a number N, and elements from 1-N are only present in the array, out of which exactly only 1 element is missing.

  2. We can make use of the formula of sum of N natural numbers from the value of N by referring the top online programming courses.

  3. We can also traverse the array and find the sum of all
    the elements in the array.

  4. Finally, the difference of the value produced by the formula and the sum value will give us our desired missing number.

Note: Take special care of type conversions between int and long long int.

ILLUSTRATION:

A[] = [1, 2, 5, 4, 6, 7]

Sum of n natural numbers = n*(n+1)/2 = 7*(7+1)/2 = 7*8/2 = 28

Sum of elements of Array = 25

Missing number = 28 - 25 = 3

SOLUTIONS:

MISNGNU

#include <stdio.h>

int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    long long n;
    scanf("%lld",&n);
    int arr[n-1];
    long long sum=0;
    long long sum_of_n = (n*(n+1))/2;
    for(int i=0;i<n-1;i++)
    {
      scanf("%d",&arr[i]);
      sum += arr[i];
    }
    printf("%lld\n",sum_of_n - sum);
  } 
  return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
  int t;cin>>t;
  while(t--)
  {
    long long n;cin>>n;
    int arr[n-1];
    long long sum=0;
    long long sum_of_n = (n*(n+1))/2;
    for(int i=0;i<n-1;i++)
    {
      cin>>arr[i];
      sum += arr[i];
    }
    long long res = sum_of_n - sum;
    cout<<res<<"\n";
  } 
  return 0;
}


import java.util.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t!=0)
    {
      int n = sc.nextInt();

      int arr[] = new int[n-1];
      long sum = 0;
      long sum_of_n = ((long)n*(n+1))/2;
      for(int i=0;i<n-1;i++)
      {
        arr[i] = sc.nextInt();
        sum += arr[i];
      }
      long res = sum_of_n - sum;
      System.out.println(res);
      t--;
    }
  }
}



Space Complexity : O(1)
Previous post Quality Factor
Next post Find Maximum

Leave a Reply

Your email address will not be published. Required fields are marked *