Find the Missing

Last Updated on December 13, 2022 by Prepbytes

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.

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:

#include 

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
						 

#include 
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>arr[i];
      sum += arr[i];
    }
    long long res = sum_of_n - sum;
    cout<

						 

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
						 

[forminator_quiz id="635"]

This article tried to discuss Basic Mathematics. Hope this blog helps you understand and solve the problem. To practice more problems on Basic Mathematics you can check out MYCODE | Competitive Programming.