අරා ලීට්කෝඩ් විසඳුමක XOR මෙහෙයුම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ වෝල්මාර්ට් ලැබ්
අරා බිට් හැසිරවීම බිටු Bitwise-XOR

ගැටළු ප්රකාශය

මෙම ගැටළුවේදී අප කළ යුත්තේ එක් එක් මූලද්‍රව්‍යය සමාන (ආරම්භක + 2 * i) ට සමාන වන n ප්‍රමාණයේ අරාවකින් XOR මෙහෙයුම කළ යුතු අතර එහිදී මම මූලද්‍රව්‍යයේ දර්ශකය (0-සුචිගත කර ඇති) සහ ආරම්භක අගය ලබා දෙනු ලැබේ.
අරාවෙහි සියලුම මූලද්‍රව්‍යයන්ගේ බිට්වේස් XOR නැවත ලබා දිය යුතුය.

උදාහරණයක්

n = 4, start = 3
8

පැහැදිලි කිරීම:

අරාව අංක [3, 5, 7, 9] ට සමාන වේ (3 ^ 5 ^ 7 ^ 9) = 8.
“^” බිට්වේස් XOR ක්‍රියාකරුට අනුරූප වේ.

n = 1, start = 7
7

පැහැදිලි කිරීම:

අරාව අංක [7] ට සමාන වේ, එබැවින් xor = 7.

ප්‍රවේශය (තිරිසන් බලය)

I = 0 සිට i = n-1 සඳහා අපට පුඩුවක් n වාරයක් ධාවනය කළ හැකිය. ලූප් සඳහා අපි විචල්ය රෙස් තුළ ගබඩා කරන වත්මන් xor සමඟ බිට්වේස් xor (ආරම්භක + 2 * i) කරන්නෙමු.

ඇල්ගොරිතම

1. අරාවෙහි මූලද්‍රව්‍යයේ දර්ශකය නිරූපණය කිරීම සඳහා විචල්ය ind එකක් සාදන්න සහ 0 සමඟ ආරම්භ කරන්න.
2. ලූප් සඳහා වත්මන් xor ගබඩා කිරීම සඳහා විචල්ය රෙස් එකක් සාදන්න සහ 0 සමඟ ආරම්භ කරන්න.
3. ind = 0 සිට ind = n-1 දක්වා පුඩුවක් සඳහා a ධාවනය කරන්න.
4. ආරම්භක + 2 * i සමඟ බිට්වේස් xor කරන්න (එනම් දර්ශක ඉන්දියාවේ මූලද්‍රව්‍යය සහ ප්‍රති result ලය res හි ගබඩා කරන්න.
5. නැවත ලබා දෙන්න.

අරා ලීට්කෝඩ් විසඳුමක XOR ක්‍රියාකාරිත්වය සඳහා ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#include <bits/stdc++.h>
using namespace std;

int xorOperation(int n, int start) {

    int ind=0;
    int res=0;
    for(ind=0;ind<n;ind++) res=res^(start+2*ind);

    return res;

}
int main() 
{
        int n=4;
        int start=3;
    cout<<xorOperation(n,start)<<endl;

  return 0; 
}
8

ජාවා වැඩසටහන

import java.lang.*;

class XorOperation
{  
    public static int xorOperation(int n, int start) 
    {

        int ind=0;
        int res=0;
        for(ind=0;ind<n;ind++) res=res^(start+2*ind);

        return res;      
    }
    
    
    public static void main(String args[])
    {
        int n=4;
        int start=3;

        System.out.println(xorOperation(n,start));
        
    }
}
8

අරා ලීට්කෝඩ් විසඳුමක XOR ක්‍රියාකාරිත්වය සඳහා සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත):  මෙහි N යනු අරාවෙහි දී ඇති ප්‍රමාණයයි. අපි N මූලද්‍රව්‍ය සඳහා ලූප සඳහා තනි අරාව හරහා ගමන් කරන විට. එබැවින් කාල සංකීර්ණතාව O (N) වේ.

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (1):  සමහර විචල්‍යයන් හැර වෙනත් අමතර මතකයක් අප භාවිතා නොකරන බැවින්. එබැවින් භාවිතා කරන අමතර ඉඩ නියත වේ.

ප්‍රවේශය (බිට් හැසිරවීම)

ඉහත ගැටලුවේදී අපට දැක ගත හැකි වන්නේ එක් එක් ඊළඟ මූලද්‍රව්‍යය අතර වෙනස 2 ක් බවයි. එය එක්තරා ආකාරයක පරාසයක් ඇති නමුත් අඛණ්ඩව නොවේ, එනම් එය විකල්ප අගයන් ඇත.

බිට් හැසිරවීම භාවිතා කිරීමෙන් අපට නියත වේලාවක අඛණ්ඩ මූලද්‍රව්‍යයන් ඇති පරාසයක බිට්වයිස් xor සොයාගත හැකිය. කෙසේ දැයි බලමු, ඉන්පසු අපි ඉහත ගැටලුව පහත ගැටලුව බවට පරිවර්තනය කිරීමට උත්සාහ කරමු:

පරාසයක් = [3,4,5,6,7,8,9,10] යැයි සිතමු, පළමු සහ අවසාන මූලද්‍රව්‍ය අතර පරාසය තුළ අපි xor යෙදිය යුතුය.

X යනු ඕනෑම ඉරට්ටේ සංඛ්‍යාවක් විය යුතු අතර y යනු xie y = x + 1 ට යාබද අංකයක් වේ. X සහ y හි xor සැමවිටම 1 ක් බව අපට පහසුවෙන් විශ්ලේෂණය කළ හැකිය. නැතහොත් ඒ අසල ඇති සෑම ඉරට්ටේ සංඛ්‍යාවක් හා ඔත්තේ සංඛ්‍යාවක් සෑම විටම 1 වේ. එබැවින් පළමු හා අවසාන සංඛ්‍යා අතර ඇති සෑම ඉරට්ටේ යුගලයක්ම xor ට සමාන බව නිගමනය කළ හැකිය. 1.
i.e.   4^5=1,  6^7=1,  8^9=1

දැන් එම යුගල ගණන අමුතු නම් 1 වන ඉරට්ටේ අංකය සහ අවසාන අමුතු අංකය අතර ඇති මූලද්‍රව්‍යවල xor 1 හෝ වෙනත් 0 වේ.
එනම් 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 = 1 ^ 1 ^ 1 = 1

දැන් අපට ඉතිරිව ඇත්තේ 3 සහ 10 යන අවසාන ස්ථානවල ඇති සංඛ්‍යා පමණි. එබැවින් අපගේ පිළිතුර පහත රූපයේ දැක්වෙන පරිදි 3 ^ 1 ^ 10 = 8 වනු ඇත:

අරා ලීට්කෝඩ් විසඳුමක XOR මෙහෙයුම

ගැටළුව අඛණ්ඩ පරාසය XOR බවට පරිවර්තනය කිරීම

ඉහත ගැටලුවේදී අප එක් එක් මූලද්‍රව්‍යය අතර දුර 2 සිට 1 දක්වා අඩු කළ හැකිය දකුණු මාරුව ටිකක් සෑම මූලද්‍රව්‍යයක්ම 1 කින් බෙදනු ලැබේ (2 න් බෙදීමට සමාන වේ). මෙය කිරීමෙන් අපි බලපාන්නේ අවසාන මූලද්‍රව්‍යයට පමණි. ඒ නිසා අපි පළමුවෙන්ම පහත දැක්වෙන අවස්ථා වලදී අපගේ අන්තිම කොටස ගබඩා කරමු:

1. අරාවෙහි ඇති සියලුම මූලද්‍රව්‍ය අමුතු නම් සහ මුළු මූලද්‍රව්‍ය ගණන ද අමුතු නම්, lastbit = 1.
2. වෙනත් lastbit = 0.

දැන් අපි සෑම මූලද්‍රව්‍යයක්ම 1 කින් නිවැරදි කළ පසු, අපගේ පරාසය මෙසේ වේ:

start / 2, start / 2 +1, start / 2 +2 ,. . . . , ආරම්භය / 2 + (n-1).

එහිදී පළමු = ආරම්භය / 2 සහ අවසාන = ආරම්භය / 2 + (n-1).

දැන් අපට මෙම පරාසයේ xor පහසුවෙන් සොයාගත හැක්කේ අවසාන මූලද්‍රව්‍යවල බිට්වේස් xor සහ ඒවා අතර ඇති ඒකාකාර යුගල සියල්ලම නියත වේලාවක සොයා ගැනීමෙනි.

Xor සොයා ගැනීමෙන් පසු අපට කළ යුතුය බිට්වේස් වම් මාරුව අපගේ අවසාන පිළිතුරෙහි බිටු වල මුල් ස්ථානය ලබා ගැනීමට ප්‍රති result ලය 1 කින්. අවසාන වශයෙන් ප්‍රති result ලයට අන්තිම බිට් එක එකතු කර එය නැවත ලබා දෙන්න.

අරා ලීට්කෝඩ් විසඳුමක XOR ක්‍රියාකාරිත්වය සඳහා ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#include <bits/stdc++.h>
using namespace std;

int xorOperation(int n, int start) {

    int lastbit;
    if(n%2==1  &&  start%2==1) lastbit=1;
    else lastbit=0;

    //after 1 right shift
    int first= start/2;
    int last= start/2+ n-1;

    int res=0;

    if(first%2==1)
    { 
        res^=first; 
        first++;
    }

    if(last%2==0)
    {
        res^=last;
        last--;
    }


    int pairs=0;            //in between pairs
    if(first<last)   pairs= (last-first+1)/2;    
    if(pairs%2==1) res^=1;   

    res<<=1;                // back to 1 left shift
    res+=lastbit;           // attaching last bit

    return res;

}
int main() 
{
        int n=4;
        int start=3;
    cout<<xorOperation(n,start)<<endl;

  return 0; 
}
8

ජාවා වැඩසටහන

import java.lang.*;

class Rextester
{  
    public static int xorOperation(int n, int start) 
    {

        int lastbit;
        if(n%2==1  &&  start%2==1) lastbit=1;
        else lastbit=0;

        //after 1 right shift
        int first= start/2;
        int last= start/2+ n-1;

        int res=0;

        if(first%2==1)
        { 
            res^=first; 
            first++;
        }

        if(last%2==0)
        {
            res^=last;
            last--;
        }


        int pairs=0;            //in between pairs
        if(first<last)   pairs= (last-first+1)/2;    
        if(pairs%2==1) res^=1;   

        res<<=1;                // back to 1 left shift
        res+=lastbit;           // attaching last bit

        return res;     
    }
    
    
    public static void main(String args[])
    {
        int n=4;
        int start=3;

        System.out.println(xorOperation(n,start));
        
    }
}
8

අරා ලීට්කෝඩ් විසඳුමක XOR ක්‍රියාකාරිත්වය සඳහා සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (1):  අපි අරාවෙහි සියලුම අංග හරහා ගමන් නොකරන බැවින්, බිටු හැසිරවීම භාවිතා කරමින් අපි එය නියත වේලාවක සිදු කර ඇත්තෙමු.

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (1):  මෙහිදී භාවිතා කරන අමතර මතකය නියත වේ.