ഒരു അറേ ലീറ്റ്കോഡ് പരിഹാരത്തിലെ XOR പ്രവർത്തനം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു വാൾമാർട്ട് ലാബുകൾ
അറേ ബിറ്റ് കൃത്രിമത്വം ബിറ്റുകൾ ബിറ്റ്വൈസ്- XOR

ഉള്ളടക്ക പട്ടിക

പ്രശ്നം പ്രസ്താവന

ഈ പ്രശ്‌നത്തിൽ‌ ഞങ്ങൾ‌ ഓരോ വലുപ്പവും തുല്യമായ (ആരംഭം + 2 * i) തുല്യമായ n ന്റെ ഒരു ശ്രേണിയിൽ‌ XOR പ്രവർ‌ത്തനം നടത്തണം, ഇവിടെ i എന്നത് മൂലകത്തിന്റെ സൂചികയും (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. അറേയുടെ ഘടകത്തിന്റെ സൂചികയെ പ്രതിനിധീകരിക്കുന്നതിന് ഒരു വേരിയബിൾ ഇൻഡന്റ് സൃഷ്ടിച്ച് 0 ഉപയോഗിച്ച് സമാരംഭിക്കുക.
2. ലൂപ്പിനായി നിലവിലെ xor സംഭരിക്കുന്നതിനും 0 ഉപയോഗിച്ച് സമാരംഭിക്കുന്നതിനും ഒരു വേരിയബിൾ റെസ് സൃഷ്ടിക്കുക.
3. ind = 0 മുതൽ ind = n-1 വരെ ലൂപ്പിനായി a പ്രവർത്തിപ്പിക്കുക.
4. ബിറ്റ്വൈസ് xor res ഉപയോഗിച്ച് (ആരംഭിക്കുക + 2 * i) അതായത് സൂചിക ഇൻഡിലെ ഘടകം, ഫലം 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 പ്രവർത്തനത്തിനുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N):  ഇവിടെ N എന്നത് അറേയുടെ തന്നിരിക്കുന്ന വലുപ്പമാണ്. N ഘടകങ്ങൾക്കായുള്ള ലൂപ്പിനായി ഒരൊറ്റ അറേയിലൂടെ സഞ്ചരിക്കുമ്പോൾ. അതിനാൽ സമയ സങ്കീർണ്ണത O (N) ആണ്.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (1):  ചില വേരിയബിളുകൾ ഒഴികെയുള്ള അധിക മെമ്മറി ഞങ്ങൾ ഉപയോഗിക്കാത്തതിനാൽ. അതിനാൽ ഉപയോഗിച്ച അധിക സ്ഥലം സ്ഥിരമാണ്.

സമീപനം (ബിറ്റ് കൃത്രിമത്വം)

മുകളിലുള്ള പ്രശ്‌നത്തിൽ ഓരോ അടുത്ത മൂലകവും തമ്മിലുള്ള വ്യത്യാസം 2 ആണെന്ന് നമുക്ക് കാണാൻ കഴിയും. അതിനർത്ഥം ഒന്നുകിൽ എല്ലാ ഘടകങ്ങളും തുല്യമായിരിക്കും അല്ലെങ്കിൽ എല്ലാം വിചിത്രമായിരിക്കും. അത് ഒരു തരം ശ്രേണിയാക്കുന്നു, പക്ഷേ തുടർച്ചയായി അല്ല, അതായത് ഇതിന് ഇതര മൂല്യങ്ങളുണ്ട്.

ബിറ്റ് കൃത്രിമത്വം ഉപയോഗിച്ച് നിരന്തരമായ ഘടകങ്ങളുള്ള നിരന്തരമായ ഘടകങ്ങളുള്ള ഒരു ശ്രേണിയുടെ ബിറ്റ്വൈസ് xor നമുക്ക് കണ്ടെത്താൻ കഴിയും. എങ്ങനെയെന്ന് നമുക്ക് നോക്കാം, തുടർന്ന് മുകളിലുള്ള പ്രശ്‌നത്തെ ചുവടെയുള്ള പ്രശ്‌നമാക്കി മാറ്റാൻ ഞങ്ങൾ ശ്രമിക്കും:

ഒരു ശ്രേണി = [3,4,5,6,7,8,9,10] എന്ന് കരുതുക, ആദ്യത്തേതും അവസാനത്തേതുമായ മൂലകങ്ങൾക്കിടയിലുള്ള ശ്രേണിയിൽ ഞങ്ങൾ xor പ്രയോഗിക്കേണ്ടതുണ്ട്.

X എന്നത് ഏതെങ്കിലും ഇരട്ട സംഖ്യയും y xie y = x + 1 ന് അടുത്തുള്ള സംഖ്യയും ആകട്ടെ. X, y എന്നിവയുടെ xor എല്ലായ്പ്പോഴും 1 ആയിരിക്കുമെന്ന് നമുക്ക് എളുപ്പത്തിൽ വിശകലനം ചെയ്യാൻ കഴിയും. അല്ലെങ്കിൽ അതിനടുത്തുള്ള എല്ലാ ഇരട്ട സംഖ്യകളുടെയും ഒറ്റ സംഖ്യയുടെയും xor എല്ലായ്പ്പോഴും 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. മറ്റ് അവസാന ബിറ്റ് = 0.

ഇപ്പോൾ ഓരോ ഘടകങ്ങളും 1 കൊണ്ട് വലത്തേക്ക് മാറ്റിയ ശേഷം, ഞങ്ങളുടെ ശ്രേണി ഇതായിരിക്കും:

ആരംഭിക്കുക / 2, ആരംഭിക്കുക / 2 +1, ആരംഭിക്കുക / 2 +2 ,. . . . , ആരംഭിക്കുക / 2 + (n-1).

ഇവിടെ ആദ്യം = ആരംഭിക്കുക / 2 ഉം അവസാനത്തേത് = ആരംഭിക്കുക / 2 + (n-1).

അന്തിമ മൂലകങ്ങളുടെ ബിറ്റ്വൈസ് xor ഉം അവയ്ക്കിടയിലുള്ള ഒറ്റ-വിചിത്ര ജോഡികളും സ്ഥിരമായ സമയത്ത് കണ്ടെത്തുന്നതിലൂടെ ഇപ്പോൾ നമുക്ക് ഈ ശ്രേണിയുടെ xor എളുപ്പത്തിൽ കണ്ടെത്താൻ കഴിയും.

Xor കണ്ടെത്തിയതിനുശേഷം ഞങ്ങൾ ചെയ്യണം ബിറ്റ്വൈസ് ഇടത് ഷിഫ്റ്റ് ഞങ്ങളുടെ അന്തിമ ഉത്തരത്തിലെ ബിറ്റുകളുടെ യഥാർത്ഥ സ്ഥാനം നേടുന്നതിന് ഫലം 1 കൊണ്ട്. അവസാനമായി ഫലത്തിലേക്ക് അവസാന ബിറ്റ് ചേർത്ത് തിരികെ നൽകുക.

ഒരു അറേ ലീറ്റ്കോഡ് പരിഹാരത്തിൽ 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 പ്രവർത്തനത്തിനുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (1):  അറേയുടെ എല്ലാ ഘടകങ്ങളിലും ഞങ്ങൾ സഞ്ചരിക്കാത്തതിനാൽ, ബിറ്റ് കൃത്രിമത്വം ഉപയോഗിച്ച് ഞങ്ങൾ അത് നിരന്തരമായ സമയത്ത് ചെയ്തു.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (1):  ഇവിടെ ഉപയോഗിച്ച അധിക മെമ്മറി സ്ഥിരമാണ്.