Find Missing Number Using Bit Manipulation

Bitwise XOR ( ^ )  takes 2 parameters, If both bits of 2 different bit patterns are different, then the XOR of both bits is 1, otherwise 0.

2 most important properties of XOR is a^0=a, a^a=0

First XOR the entire array, then XOR the result from starting to end of the array. Sence a^a=0, hence all duplicates will cancel out each other, only missing integer will remain.

package org.wesome.dsalgo;

public class FindMissingNumber {
    public static int findMissingNumber(int[] arr, int start, int end) {
        int xor = 0;
        for (int i : arr) {
            xor = xor ^ i;
        }
        for (int i = start; i <= end; i++) {
            xor = xor ^ i;
        }
        return xor;
    }
}

package org.wesome.dsalgo;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class FindMissingNumberTest {
    @Test
    void findMissingNumberTest1() {
        int[] intArr = {1, 3, 4, 5};
        Assertions.assertEquals(2, FindMissingNumber.findMissingNumber(intArr, 1, 5));
    }

    @Test
    void findMissingNumberTest2() {
        int[] intArr = new int[]{5, 6, 8, 9, 10};
        Assertions.assertEquals(7, FindMissingNumber.findMissingNumber(intArr, 5, 10));
    }

    @Test
    void findMissingNumberTest3() {
        int[] intArr = new int[]{11, 12, 14, 15};
        Assertions.assertEquals(13, FindMissingNumber.findMissingNumber(intArr, 11, 15));
    }
}

plugins {
    id 'java'
}

group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8

configurations {
    compileOnly {
        extendsFrom annotationProcessor
    }
}

repositories {
    mavenCentral()
}

dependencies {
    testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}

test {
    useJUnitPlatform()
}