Last active
October 28, 2020 22:06
-
-
Save Ch-sriram/cb806b62ef953ea16dae6975326a4818 to your computer and use it in GitHub Desktop.
Missing Number in Array [TC: O(N); SC: O(1)]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Problem Link: https://practice.geeksforgeeks.org/problems/missing-number-in-array1416/1 | |
int MissingNumber(vector<int>& ar, int n) { | |
// Find XOR of all integers from 1 to n | |
int XORn = 0; | |
for(int i = 1; i <= n; ++i) | |
XORn ^= i; | |
// Find XOR of all integers in ar[] | |
int XORar = 0; | |
for(int i = 0; i < (int)ar.size(); ++i) | |
XORar ^= ar[i]; | |
// Return XOR of XORn and XORar | |
return XORn ^ XORar; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Problem Link