የ XOR ኦፕሬሽን በድርድር Leetcode መፍትሔ ውስጥ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የዎልማርት ላብራቶሪዎች
ሰልፍ ቢት ማባከን ቢት ቢትራሾ-XOR

የችግሩ መግለጫ

በዚህ ችግር ውስጥ እያንዳንዱ ንጥረ ነገር (ጅምር + 2 * i) በሚሆንበት የ ‹XOR ኦፕሬሽን› መጠን ባለው n ውስጥ ማድረግ አለብን (መነሻ -0 + i *) እና የመነሻ ዋጋ ተሰጥቷል ፡፡
ከድርድሩ ሁሉንም ንጥረ ነገሮች በትንሹ ወደኋላ መመለስ አለብን።

ለምሳሌ

n = 4, start = 3
8

ማብራሪያ:

የድርድር ቁጥሮች ከ [3 ፣ 5 ፣ 7 ፣ 9] ጋር እኩል ነው (3 ^ 5 ^ 7 ^ 9) = 8።
“^” ከብልት XOR ኦፕሬተር ጋር የሚዛመድበት ቦታ።

n = 1, start = 7
7

ማብራሪያ:

የድርድር ቁጥሮች ከ [7] ጋር እኩል ነው ፣ ስለሆነም xor = 7።

አቀራረብ (የጭካኔ ኃይል)

እኛ በቀላሉ ለ ‹loop n› ጊዜያት ለ i = 0 እስከ i = n-1 ማስኬድ እንችላለን ፡፡ ለሉፕ (ተለዋዋጭ) ውስጥ የምናስቀምጠውን የአሁኑን ፍሬ (ጅምር + 2 * i) በመጠኑም ቢሆን ነፃ እናደርጋለን ፡፡

አልጎሪዝም

1.የድርጅቱን ንጥረ-ነገር ጠቋሚ ለመወከል ተለዋዋጭ ኢንዲን መፍጠር እና በ 0 መጀመር።
2. በሉፍ ጊዜ የአሁኑን xor ለማከማቸት ተለዋዋጭ ሬንጅ መፍጠር እና በ 0 መጀመር ፡፡
3. ለ loop ከ ‹ኢን = 0 እስከ ind = n-1› ያሂዱ ፡፡
4. የ ‹ቢዝነስ› መብትን በ (ጅምር + 2 * i) ማለትም በመረጃ ጠቋሚ ኢንዴክስ ላይ ያካሂዱ እና ውጤቱን በቅዳሜ ያከማቹ
5. ሬሳውን ይመልሱ ፡፡

ለ ‹XOR› አሠራር በድርድር ሌትኮድ መፍትሔ ውስጥ መተግበር

C ++ ፕሮግራም

#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

በድርድር Leetcode መፍትሄ ውስጥ ለ ‹XOR› ክወና ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን)  N የተሰጠው የድርድር መጠን የት ነው። ለ N አባሎች ቀለበት በአንድ ረድፍ ላይ ድርድርን ስናልፍ ፡፡ ስለዚህ የጊዜ ውስብስብነት O (N) ነው።

የቦታ ውስብስብነት 

ኦ (1)  ከአንዳንድ ተለዋዋጮች ሌላ ማንኛውንም ተጨማሪ ማህደረ ትውስታ ስለማንጠቀም ፡፡ ስለዚህ ጥቅም ላይ የዋለው ተጨማሪ ቦታ ቋሚ ነው።

አቀራረብ (ቢት ማባከን)

ከላይ በተጠቀሰው ችግር ውስጥ በእያንዳንዱ ቀጣይ ንጥረ ነገር መካከል ያለው ልዩነት መሆኑን ማየት እንችላለን 2. ያም ማለት ሁሉም ንጥረ ነገሮች እኩል ይሆናሉ ወይም ሁሉም ያልተለመዱ ይሆናሉ ማለት ነው። ያ አንድ ዓይነት ክልል ያደርገዋል ግን ተከታታይ አይደለም ማለትም ተለዋጭ እሴቶች አሉት ማለት ነው።

ቢት ማጭበርበርን በመጠቀም በቋሚነት በውስጡ ተከታታይ ንጥረ ነገሮችን የያዘ የርዝመት አቅጣጫን ትንሽ ማግኘት እንችላለን። እስቲ እስቲ እንመልከት ፣ ከዚያ ከላይ ያለውን ችግር ወደ ታች ወደ ችግሩ ለመለወጥ እንሞክራለን

ክልል = [3,4,5,6,7,8,9,10] እንበል ፣ እና በመጀመሪያ እና በመጨረሻው ንጥረ ነገር መካከል ባለው ክልል ውስጥ xor ማመልከት አለብን።

X ማንኛውም እኩል ቁጥር ይሁን እና ከ xie y = x + 1 ቀጥሎ ያለው ቁጥር ይሁን። ያ የ x እና y ነፃነት በቀላሉ እንደሚከተለው መተንተን እንችላለን 1. ወይም ደግሞ የእያንዳንዱን ቁጥር እና ጎዶሎ ቁጥር ቁጥር ሁልጊዜ ነው 1. ስለሆነም በመጀመሪያ እና በመጨረሻው ቁጥር መካከል ያሉ ያልተለመዱ ያልተለመዱ ጥንዶች እኩል እኩል ይሰጡናል ብለን መደምደም እንችላለን 1.
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 ^ 1 ^ 10 = 8 ይሆናል ፡፡

የ XOR ኦፕሬሽን በድርድር Leetcode መፍትሔ ውስጥ

ችግሩን ወደ ተከታታይ ክልል XOR መለወጥ

ከላይ በተጠቀሰው ችግር እኛ ከሆንን በእያንዳንዱ ንጥረ ነገር መካከል ያለውን ርቀት ከ 2 ወደ 1 መቀነስ እንችላለን የቀኝ ፈረቃ በትንሹ እያንዳንዱ ንጥረ ነገር በ 1 (በ 2 በመከፋፈል ተመሳሳይ)። ይህንን በማድረጋችን የመጨረሻውን የንጥረ ነገሮች ላይ ብቻ ተጽዕኖ እያሳደረን ነው። ስለዚህ በመጀመሪያ የሚከተሉትን የመጨረሻዎቻችንን በሚከተሉት ጉዳዮች እናከማቸዋለን-

1. በምድቡ ውስጥ ያሉት ሁሉም ንጥረ ነገሮች ያልተለመዱ እና የጠቅላላው ንጥረ ነገሮች ብዛት ያልተለመዱ ከሆኑ ከዚያ lastbit = 1።
2. ሌላ ላስቲቢት = 0.

አሁን እያንዳንዱን ንጥረ ነገር በ 1 ከቀየርን በኋላ የእኛ ክልል ይሆናል-

ጀምር / 2 ፣ ጀምር / 2 +1 ፣ ጀምር / 2 +2 ፣. . . . ፣ ይጀምሩ / 2 + (n-1)።

የት መጀመሪያ = ጅምር / 2 እና የመጨረሻ = ጅምር / 2 + (n-1)።

የመጨረሻ ነጥቦችን እና በመካከላቸው ያሉትን ያልተለመዱ ጥንዶች በቋሚነት በማግኘት የዚህን ክልል ነፃነት በቀላሉ ማግኘት እንችላለን ፡፡

Xor ካገኘን በኋላ ማድረግ አለብን በትንሹ አቅጣጫ ግራ ፈረቃ በመጨረሻው መልሳችን የመጀመሪያዎቹን የቢቶች አቋም ለማግኘት ውጤቱ በ 1 ፡፡ በመጨረሻም የመጨረሻውን ሂሳብ በውጤቱ ላይ ይጨምሩ እና ይመልሱ።

ለ ‹XOR› አሠራር በድርድር ሌትኮድ መፍትሔ ውስጥ መተግበር

C ++ ፕሮግራም

#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

በድርድር Leetcode መፍትሄ ውስጥ ለ ‹XOR› ክወና ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (1)  ሁሉንም የደርቢው አካላት እየተሻገርን ባለመሆኑ ፣ ቢት ማጭበርበርን በመጠቀም በቋሚ ጊዜ አደረግነው ፡፡

የቦታ ውስብስብነት 

ኦ (1)  እዚህ በተጨማሪ ጥቅም ላይ የዋለው ተጨማሪ ማህደረ ትውስታ ቋሚ ነው።