Thursday, 10 June 2021

How to find the missing number from a given array (when only one number is missing from a sequence of non-zero numbers)?

Assumptions :

The array may have only one number missing in the sequence of numbers
with out zero in it.
Example:
int[] arr= {1, 3};
The missing number is 2 (where numbers are from 1 to 3)
Algorithm:
> Calculate the array size, using array size - calculate the sum of n numbers 
(n: array size + 1)
> Traverse the array elements using a for loop - calculate the moving sum
> then after that, diff of number of n numbers - moving sum of elements will 
give the missing number
Example:
package com.algos;

public class OnlyMissingNumberInArray {

public static void main(String[] args) {
int[] arr= {1, 3};
//The missing number from 1 to 3 is 2
System.out.println("The missing number "+ findMissingNumber(arr));
}

private static int findMissingNumber(int[] arr) {
//Calculate sum of numbers from 1 to 3 using n(n+1)/2
int n = arr.length + 1;
int sumOf = n * (n + 1)/2;
int sum = 0;
for(int i : arr) {
sum = sum + i; //moving sum
}
return sumOf - sum; //missing number 2
}
}

No comments:

Post a Comment