Redirecting to
NADOS


  Prev   Next

ONE REPEATING AND ONE MISSING







"Things which matter most must never be at the mercy of things which matter least."
Shreeya Gupta

{{!--topic name --}}

Hey there coder. The question we are going to discuss in this article is a continuation of the previous question, "All Repeating Except Two". So, check out that question first before attempting this question.

Importan Link : Problem Link, Solution Video Link

Understanding Problem

    " You are given an array of length n containing numbers from 1 to n. " One number is present twice in the array and one is missing. " You have to find these two numbers.

Say, if n=7, then the array of numbers should have been something like [3,6,2,5,1,4,7].

Here all the numbers from 1 to 7 are appearing.

But, we are given an array [3,6,2,5,1,2,7]. In this array, the element '2' repeats itself and is present in the place of element '4'. So, we are supposed to print both the missing as well as the repeating number.

Reader, we can't use the XOR directly on the input array because it requires duplicacy. If we use XOR on [3,6,2,5,1,2,7], the duplicate 2's will cancel each other and we will be left with 3^6^5^1^7 which solves no purpose.

APPROACH

Dear coder, to cancel the duplicacy of all the elements of the array such that only the missing and repeating numbers remain, we XOR the input array, [3,6,2,5,1,2,7] along with additional elements from 1 to 7.

img

When we apply XOR on all the elements in figure1, all the duplicate elements will get cancelled with each other as shown in img_2.

img

In the above figure, duplicates of 1,3,5,6 and 7 get cancelled with each other. Also the duplicates of 2 gets cancelled with each other and the additional element 2 is left along with the missing number 4 because 4 had no duplicates.

Hence, we are left with 2^4.

CODE

If you have understood the approach, you should attempt to code it yourself.

After giving it a fair try, check out the code we have provided too.

import java.io.*; import java.util.*; public class Main { public static void main(String[] args){ Scanner scn = new Scanner(System.in); int n = scn.nextInt(); int[] arr = new int[n]; for(int i = 0 ; i < n; i++){ arr[i] = scn.nextInt(); } solution(arr); } public static void solution(int[] arr){ int xor=0; for(int i=0;i < arr.length;i++){ xor^=arr[i]; } for(int i=1;i<= arr.length;i++){ xor^=i; } int rsb=xor & -xor; int x=0; int y=0; for(int val:arr){ if((val&rsb)==0){ x=x^val; }else{ y=y^val; } } for(int i=1;i <= arr.length;i++){ if((i&rsb) == 0){ x = x^i; }else{ y = y^i; } } for(int val:arr){ if(val==x){ System.out.println("Missing Number -> "+y); System.out.println("Repeating Number -> "+x); break; }else if(val==y){ System.out.println("Missing Number -> "+x); System.out.println("Repeating Number -> "+y); break; } } } }

If you have studied the previous problems carefully, you will find this code fairly straightforward.

In case you still face any problem, just watch the solution video.
java; true";
Time ans Space Complexity
Time Complexity

TIME COMPLEXITY- O(n)

Space Complexity

SPACE COMPLEXITY-O(1)

ONE REPEATING AND ONE MISSING
Author: Shreeya Gupta
 
Run
Id Name