એરે લીટકોડ સોલ્યુશનમાં XOR ઓપરેશન  


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે વોલમાર્ટ લેબ્સ
ગાણિતીક નિયમો અરે બિટ મેનિપ્યુલેશન બિટ્સ બિટવાઇઝ-એક્સઓઆર કોડિંગ મુલાકાત ઇન્ટરવ્યુની તૈયારી લેટકોડ LeetCodeSolutions

સમસ્યા નિવેદન  

આ સમસ્યામાં આપણે કદના એરેમાં XOR ઓપરેશન કરવું પડશે જેમાં દરેક તત્વ બરાબર છે (પ્રારંભ + 2 * i) જ્યાં હું તત્વની અનુક્રમણિકા છે (0-અનુક્રમિત) અને પ્રારંભનું મૂલ્ય આપવામાં આવે છે.
આપણે એરેના બધા તત્વોના બીટવાઇઝ એક્સઓઆરને પાછા આપવું પડશે.

ઉદાહરણ

n = 4, start = 3
8

સમજૂતી:

એરે નંબર્સ [3, 5, 7, 9] ની બરાબર છે જ્યાં (3 ^ 5 ^ 7 ^ 9) = 8.
જ્યાં “^” બીટવાઇઝ એક્સઓઆર ઓપરેટરને અનુરૂપ છે.

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 સુધી લૂપ માટે ચલાવો.
Res. રેઝનો બીટવાઇઝ ઝોર કરો (પ્રારંભ કરો + 4 * i) એટલે કે તત્વ અનુક્રમણિકામાં અને પરિણામે રેઝમાં સંગ્રહિત કરો.
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

એરે લીટકોડ સોલ્યુશનમાં એક્સઓઆર ઓપરેશન માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન):  જ્યાં એન એરેનું આપેલ કદ છે. જેમ કે આપણે N એલિમેન્ટ્સ માટે લૂપ ફોર લૂપલમાં એરેને ટ્રversસ કરી રહ્યા છીએ. તેથી સમય જટિલતા ઓ (એન) છે.

અવકાશ જટિલતા 

ઓ (1):  કારણ કે આપણે કેટલાક ચલો સિવાયની કોઈ વધારાની મેમરીનો ઉપયોગ કરી રહ્યા નથી. તેથી વપરાયેલી વધારાની જગ્યા સતત છે.

અભિગમ (બિટ મેનિપ્યુલેશન 

ઉપરની સમસ્યામાં આપણે જોઈ શકીએ છીએ કે દરેક આગલા તત્વ વચ્ચેનો તફાવત 2 છે. તેનો અર્થ એ કે કાં તો બધા તત્વો સરખા હશે અથવા બધા વિચિત્ર હશે. તે એક પ્રકારની શ્રેણી બનાવે છે પરંતુ સળંગ નહીં એટલે કે તેમાં વૈકલ્પિક મૂલ્યો છે.

બીટ મેનીપ્યુલેશનનો ઉપયોગ કરીને આપણે તેને સતત સમયમાં સતત તત્વો ધરાવતા શ્રેણીના બીટવાઇઝ ઝોર શોધી શકીએ છીએ. ચાલો જોઈએ કે કેવી રીતે, અને પછી આપણે ઉપરની સમસ્યાને નીચેની સમસ્યામાં રૂપાંતરિત કરવાનો પ્રયાસ કરીશું:

ચાલો માની લઈએ કે શ્રેણી = [3,4,5,6,7,8,9,10], અને આપણે પ્રથમ અને છેલ્લા તત્વ વચ્ચેની શ્રેણીમાં xor લાગુ કરવું પડશે.

ચાલો x એ કોઈપણ સમાન સંખ્યા હોઈ શકે અને y એ xie y = x + 1 ની બાજુમાંનો નંબર હોય. આપણે x અને y નો xor હંમેશાં 1 હશે તેવું વિશ્લેષણ કરી શકીએ છીએ. અથવા તે પછીની દરેક સમાન સંખ્યાની સંખ્યા અને તેની આગળની વિચિત્ર સંખ્યા હંમેશાં 1 હોય છે. તેથી આપણે નિષ્કર્ષ લઈ શકીએ કે પ્રથમ અને છેલ્લી સંખ્યાની વચ્ચેની દરેક-વિચિત્ર જોડીઓ xor સમાન બરાબર આપે છે. ..
i.e.   4^5=1,  6^7=1,  8^9=1

આ પણ જુઓ
જ્વેલ્સ અને સ્ટોન્સ લીટકોડ સોલ્યુશન

હવે જો આ જોડીની સંખ્યા વિચિત્ર હોય તો 1 લી બરાબર સંખ્યા અને છેલ્લી વિચિત્ર સંખ્યા વચ્ચેના તત્વોની ઝોર 1, અથવા અન્ય 0 હશે.
એટલે કે 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 = 1 ^ 1 ^ 1 = 1

હવે આપણી પાસે ફક્ત અંતિમ સ્થાનો પરની સંખ્યા બાકી છે જે 3 અને 10 છે તેથી નીચે આપેલા આંકડામાં બતાવ્યા પ્રમાણે આપણો જવાબ 3 below 1 figure 10 = 8 હશે:

એરે લીટકોડ સોલ્યુશનમાં XOR ઓપરેશન

સમસ્યાને સતત રેંજ XOR માં રૂપાંતરિત કરી રહ્યું છે

ઉપરોક્ત સમસ્યામાં આપણે દરેક તત્વ વચ્ચેનું અંતર 2 થી 1 ઘટાડી શકીએ છીએ જો આપણે જમણી પાળી થોડી દિશામાં દરેક તત્વ 1 દ્વારા (2 દ્વારા ભાગાકાર કરવા જેટલું જ). આ કરીને આપણે ફક્ત તત્વોના છેલ્લા બીટને અસર કરી રહ્યા છીએ. તેથી અમે નીચે આપેલા કેસો દ્વારા પહેલા અમારા જવાબોનો છેલ્લો બીટ સંગ્રહિત કરીએ છીએ:

1. જો એરેમાંના બધા તત્વો વિચિત્ર હોય અને તત્વોની કુલ સંખ્યા પણ વિચિત્ર હોય, તો પછી લાસ્ટબિટ = 1.
2. બીજું લાસ્ટબિટ = 0.

હવે આપણે દરેક તત્વને 1 દ્વારા શીર્ષક પછી, અમારી શ્રેણી બને છે:

પ્રારંભ / 2, પ્રારંભ / 2 +1, પ્રારંભ / 2 +2,. . . . , પ્રારંભ કરો / 2 + (એન -1).

જ્યાં પ્રથમ = પ્રારંભ / 2 અને છેલ્લું = પ્રારંભ / 2 + (n-1).

હવે આપણે અંતિમ તત્વોના બીટવાઇઝ ઝોર અને સતત સમયની વચ્ચે તેમની વચ્ચેની બધી સમાન-વિચિત્ર જોડી શોધીને સરળતાથી આ રેંજનો ઝોર શોધી શકીએ છીએ.

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

એરે લીટકોડ સોલ્યુશનમાં એક્સઓઆર ઓપરેશન માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (1):  જેમ કે આપણે એરેના બધા તત્વો પર આગળ ન જતા હોઈએ છીએ, બીટ મેનીપ્યુલેશનનો ઉપયોગ કરીને અમે તેને સતત સમયમાં કરી દીધું છે.

આ પણ જુઓ
તફાવત લીટકોડ સોલ્યુશન શોધો

અવકાશ જટિલતા 

ઓ (1):  અહીં પણ વપરાયેલી વધારાની મેમરી સતત છે.