TwoMissingNumberInArray.java

packagearray;

publicclassTwoMissingNumberInArray {

// O(N) time | O(N) space
publicstaticvoidprintTwoMissingNumbers(int[] arr) {
intn = arr.length + 2;
// initialized with zero
int[] binaryArr = newint[n + 1];

// set 1 in binaryArr for existing items in arr
for (intnum : arr) {
binaryArr[num] = 1;
 }
// print missing numbers
for (inti = 1; i <= n; i++) {
if (binaryArr[i] == 0) {
System.out.println(i);
 }
 }
 }

// O(N) time | O(1) Space
publicstaticvoidfindMissingTwo(int[] arr) {
intn = arr.length + 2;

inttotalSum = n * (n + 1) / 2;
intarraySum = 0;

for (intnum : arr) {
arraySum += num;
 }
intmissingSum = totalSum - arraySum;
intmissingAverage = missingSum / 2;

intmissingAvgSum = missingAverage * (missingAverage + 1) / 2;
intfirstMissing = totalSum - missingAvgSum;
intsecondMissing = missingSum - firstMissing;

System.out.println(firstMissing);
System.out.println(secondMissing);
 }

publicstaticvoidfindMissingTwoXORapproach(int[] arr) {

intn = arr.length;
intmissingXOR = n + 2; // [1, n+2] range of arr distinct items

// finding xor of two missing elements
for (inti = 0; i < n; i++) {
missingXOR = missingXOR ^ arr[i]; // xored with all array items
missingXOR = missingXOR ^ (i + 1); // xored in range 1 to n + 2
 }
missingXOR = missingXOR ^ (n + 1);

// finding the set bit, & then grouping based on bit is set or not in
// that position
// using left shift operation on 1 to get the set bit position, in LSB
intsetBitPosition = 0;
for (inti = 0; i < 32; i++) {
if ((missingXOR & (1 << i)) != 0) {
setBitPosition = i;
break;
 }
 }

// grouping based on set bit position, if setBitPosition is set or not
intgroup1 = 0, group2 = 0, setBitNumber = 1 << setBitPosition;

// checking set bit in array items
for (inti = 0; i < arr.length; i++) {
if ((arr[i] & setBitNumber) == 0) {
group1 = group1 ^ arr[i]; // bit is set
 } else {
group2 = group2 ^ arr[i]; // bit is not set
 }
 }

// checking set bit in range 1 to n+2
for (inti = 1; i <= n + 2; i++) {
if ((i & setBitNumber) == 0) {
group1 = group1 ^ i; // bit is set
 } else {
group2 = group2 ^ i; // bit is not set
 }
 }

System.out.println(group1);
System.out.println(group2);
 }

publicstaticvoidmain(String[] args) {
// printTwoMissingNumbers(new int[] { 2, 1, 3, 5 });
// findMissingTwo(new int[] { 2, 1, 4 });
// findMissingTwoXORapproach(new int[] { 2, 1, 4 });
findMissingTwoXORapproach(newint[] { 2, 3, 4, 5 });
 }
}