Skip to content

Instantly share code, notes, and snippets.

@Ch-sriram
Last active October 28, 2020 22:06
Show Gist options
  • Save Ch-sriram/cb806b62ef953ea16dae6975326a4818 to your computer and use it in GitHub Desktop.
Save Ch-sriram/cb806b62ef953ea16dae6975326a4818 to your computer and use it in GitHub Desktop.
Missing Number in Array [TC: O(N); SC: O(1)]
// 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;
}
@Ch-sriram
Copy link
Author

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment