Xor of N numbers-javaTutorial-php.cn

Xor of N numbers

Patricia Arquette

Release： 2024-09-21 20:15:32

Original

273 people have browsed it

Xor of N numbers

Given an integer number N, find the exor of the range 1 to N
exor of 1 ^ 2 ^ 3 ^4 ^.....N;

Brute force approach:
Tc:O(n)
Sc:O(1)

public int findExor(int N){

        //naive/brute force approach:
        int val  = 0;
        for(int i=1;i<5;i++){
            val =  val^ i;
        }
        return val;
    }

Copy after login

Optimal approach:
Tc:O(1)
Sc:O(1)

    public int getExor(int N){
        //better approach

        /**
         * one thing to observe is 
         * 1 = 001  = 1
         * 1 ^2 = 001 ^ 010 = 011=       3
         * 1^2^3 = 011 ^ 011 = 0=        0
         * 1^2^3^4 = 000^100 = 100=      4
         * 1^2^3^4^5 = 100^101 = 001=    1
         * 1^2^3^4^5^6 = 001^110 =111=   7
         * 1^2^3^4^5^6^7 = 111^111=000=  0
         * 
         * what we can observer is : 
         * 
         * N%4==0 then result is: N
         * N%4 ==1 then result is: 1
         * N%4 ==2 then result is: N+1
         * N%4==3 then result is: 0
         * 
         * */
         if(N%4==0) return N;
         else if(N%4 ==1) return 1;
         else if(N%4==2) return N+1;
         else return 0;

    }

Copy after login

What if we have to find the exor between ranges like L and R
example find an exor between numbers 4 and 7 i.e. 4^5^6^7.

For solving this we can leverage the same optimal solution above getExor()

first we will get exor till L-1 i.e getExor(L-1) = 1 ^ 2 ^ 3 (since L-1 = 3)......equation(1)

then we will find getExor(R) = 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ----equation(2)

the finally,

Result  = equation(1) ^ equation(2)
        = (1 ^ 2 ^ 3) ^ (1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7)
        = (4^5^6^7)

Copy after login

public int findExorOfRange(int L, int R){
        return getExor(L-1) ^ getExor(R);
    }

public int getExor(int N){
        //better approach

        /**
         * one thing to observe is 
         * 1 = 001  = 1
         * 1 ^2 = 001 ^ 010 = 011=       3
         * 1^2^3 = 011 ^ 011 = 0=        0
         * 1^2^3^4 = 000^100 = 100=      4
         * 1^2^3^4^5 = 100^101 = 001=    1
         * 1^2^3^4^5^6 = 001^110 =111=   7
         * 1^2^3^4^5^6^7 = 111^111=000=  0
         * 
         * what we can observer is : 
         * 
         * N%4==0 then result is: N
         * N%4 ==1 then result is: 1
         * N%4 ==2 then result is: N+1
         * N%4==3 then result is: 0
         * 
         * */
         if(N%4==0) return N;
         else if(N%4 ==1) return 1;
         else if(N%4==2) return N+1;
         else return 0;

    }

Copy after login

The above is the detailed content of Xor of N numbers. For more information, please follow other related articles on the PHP Chinese website!