Xor von N Zahlen

Gegeben eine ganze Zahl N, finden Sie den Exor des Bereichs 1 bis N
exor von 1 ^ 2 ^ 3 ^4 ^.....N;

Brute-Force-Ansatz:
Tc:O(n)
Sc:O(1)

public int findExor(int N){

        //naive/brute force approach:
        int val  = 0;
        for(int i=1;i



<p>Optimaler Ansatz:<br>
Tc:O(1)<br>
Sc:O(1)<br>
</p>

<pre class="brush:php;toolbar:false">
    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;

    }

Was wäre, wenn wir den Exor zwischen Bereichen wie L und R finden müssten?
Finden Sie beispielsweise ein Exor zwischen den Zahlen 4 und 7, d. h. 4^5^6^7.

Um dieses Problem zu lösen, können wir die gleiche optimale Lösung wie oben bei getExor() nutzen

Zuerst erhalten wir exor bis L-1, d. h. getExor(L-1) = 1 ^ 2 ^ 3 (da L-1 = 3)......Gleichung(1)

Dann finden wir getExor(R) = 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ----Gleichung(2)

das Endlich,

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

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;

    }

Das obige ist der detaillierte Inhalt vonXor von N Zahlen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!