Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 4 Jan, 2021

Find The Repeating And Missing Number

Easy
Asked in companies
AmazonSamsungPhone Pe

Problem statement

You are given an array 'nums' consisting of first N positive integers. But from the N integers, one of the integers occurs twice in the array, and one of the integers is missing. You need to determine the repeating and the missing integer.

Example:
Let the array be [1, 2, 3, 4, 4, 5]. In the given array ‘4’ occurs twice and the number ‘6’ is missing.
Input format:
The very first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains an integer ‘N’ denoting the number of elements present in the array.

The second line of every test case contains ‘N’ space-separated integers denoting the elements present in the array.
Output format:
For each test case, print the two space-separated integers denoting the repeating and the missing numbers, in the same order.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function. 
Follow Up:
Can you solve this in O(N) time and O(1) space complexities?
Constraints:
1 <= T <= 100 
2 <= N <= 10^4
1 <= nums[i] <= N

Time Limit: 1 sec

Approaches

01 Approach

  • A simple and intuitive approach could be to sort the given array in ascending order.
  • Now, in order to determine the repeating  and the missing numbers, we check the adjacent pair of elements.
  • If two numbers are equal and are adjacent to each other, it implies that the number occurs twice. Hence, it is the repeating number.
  • In order to determine the missing element, we maintain a counter.
  • The counter holds the next expected number in the array. So, initially counter holds 1.
  • Now, we iterate through the array.
  • If the current number is equal to the counter,
    • We increment the counter.
    • And check if the current number is the repeating number. If so, we skip the next number.
    • Otherwise, move to the next number.
  • Otherwise, if the current number is not equal to the counter, we have found the missing number.
    • The counter holds the missing number.
  • Return the repeating and the missing number.