Find Element Which Appears Only Once and Every Other Element Appears Thrice 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 property of XOR is a^0=a, a^a=0

let's take the example of { 4 , 3 , 3 , 3 }

4 in binary = 1 0 0
3 in binary = 0 1 1
3 in binary = 0 1 1
3 in binary = 0 1 1

sum of bits = 1 3 3

1 % 3 = 1

3 % 3 = 0

3 % 3 = 0

binary 1 0 0 in digit will be 4 . hence 4 appeared only once.

package org.wesome.dsalgo;

public class FindElementAppearOnce {
    public static int findElementAppearOnce(int[] arr) {
        int onceElement = 0;
        /*  integer requires 32 bit, hence loop from 1 to 32 so that it will calculate for every position in 32-bit integer  */
        for (int intIndx = 0; intIndx < 32; intIndx++) {
            int rightShift = (1 << intIndx);
            System.out.println("1 after " + intIndx + " right shift = " + Integer.toBinaryString(rightShift));
            int tempSum = 0;
            for (int arrIndx = 0; arrIndx < arr.length; arrIndx++) {
                System.out.println(arr[arrIndx] + " in binary form = " + Integer.toBinaryString(arr[arrIndx]));
                int andWithOne = (arr[arrIndx] & rightShift);
                System.out.println(Integer.toBinaryString(arr[arrIndx]) + " after & With " + rightShift + " in binary = " + Integer.toBinaryString(andWithOne));
                /*  if ith bit is set then & will return in 1 else 0    */
                if (andWithOne >= 1) {
                    /*  for each ith set bit, increment tempSum */
                    System.out.println("tempSum before increment = " + Integer.toBinaryString(tempSum));
                    tempSum = tempSum + 1;
                    System.out.println("tempSum after increment = " + Integer.toBinaryString(tempSum));
                }
            }
            /*  if the ith bit is not multiple of 3, it means ith bit belongs to element that appeared once only    */
            if ((tempSum % 3) == 1) {
                /*  generate the integer from binary    */
                onceElement = onceElement | rightShift;
            }
        }
        System.out.println("Element appearing once is: " + onceElement + "\n");
        return onceElement;
    }
}

package org.wesome.dsalgo;

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

import static org.wesome.dsalgo.FindElementAppearOnce.findElementAppearOnce;


public class FindElementAppearOnceTest {
    @Test
    void FindElementAppearOnceTest1() {
        int arr[] = {1, 2, 2, 2, 3, 3, 3};
        Assertions.assertEquals(1, findElementAppearOnce(arr));
    }

    @Test
    void FindElementAppearOnceTest2() {
        int arr[] = {3, 3, 3, 2, 2, 2, 1};
        Assertions.assertEquals(1, findElementAppearOnce(arr));
    }
}

plugins {
    id 'java'
    id "io.freefair.lombok" version "6.2.0"
}

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()
}