XOR אָפּעראַציע אין אַן Array Leetcode לייזונג


שוועריקייט לעוועל גרינג
אָפט געבעטן אין וואַלמאַרט לאַבס
מענגע ביסל מאַניפּיאַליישאַן ביץ ביטוויסע-קסאָר

פּראָבלעם סטאַטעמענט

אין דעם פּראָבלעם, מיר דאַרפֿן צו מאַכן XOR אָפּעראַציע אין אַ נומער פון גרייס n, אין וואָס יעדער עלעמענט איז גלייַך צו (אָנהייב + 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.

צוגאַנג (ברוט פאָרס)

מיר קענען סימפּלי לויפן a for loop n times פֿאַר i = 0 to i = n-1. אין דעם שלייף, מיר טאָן ביטווייז קסאָר פון (אָנהייב + 2 * איך) מיט דעם קראַנט קסאָר וואָס מיר וועלן קראָם אין אַ בייַטעוודיק רעז.

אַלגאָריטהם

1. שאַפֿן אַ בייַטעוודיק ינד צו פאָרשטעלן אינדעקס פון די עלעמענט פון דער מענגע און יניטיאַליזירן מיט 0.
2. שאַפֿן אַ וועריאַבלע רעס צו קראָם דעם קראַנט קסאָר בעשאַס פֿאַר שלייף און יניטיאַליזירן מיט 0.
3. לויפן אַ פֿאַר שלייף פון ינד = 0 צו ינד = n-1.
4. טאָן ביטווייז קסאָר פון ריס מיט (אָנהייב + 2 * איך) הייסט עלעמענט ביי אינדעקס ינד און קראָם די רעזולטאַט אין רעס.
5. צוריקקומען די רעז.

ימפּלאַמענטיישאַן פֿאַר קסאָר אָפּעראַציע אין אַן Array Leetcode לייזונג

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

Java פּראָגראַם

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 אָפּעראַציע אין אַן Array Leetcode לייזונג

צייט קאַמפּלעקסיטי

אָ (N):  וווּ N איז די געגעבן גרייס פון די מענגע. ווי מיר פאָרן די מענגע אין איין פֿאַר שלייף פֿאַר ע עלעמענטן. דעריבער צייט קאַמפּלעקסיטי איז אָ (ען).

ספעיס קאַמפּלעקסיטי 

אָ (1):  ווייַל מיר נוצן קיין עקסטרע זכּרון אנדערע ווי עטלעכע וועריאַבאַלז. דעריבער אַן עקסטרע נוצן פּלאַץ איז קעסיידערדיק.

צוגאַנג (ביסל מאַניפּיאַליישאַן)

אין דעם אויבן פּראָבלעם מיר קענען זען אַז די חילוק צווישן יעדער ווייַטער עלעמענט איז 2. אַז מיטל אַז אַלע די יסודות וועט זיין גלייך אָדער אַלע וועלן זיין מאָדנע. דאָס איז אַ סאָרט פון אַ קייט, אָבער נישט קאָנסעקוטיווע, דאָס הייסט אָלטערנאַטיוו וואַלועס.

ניצן ביסל מאַניפּיאַליישאַן מיר קענען געפֿינען ביטווייז קסאָר פון אַ קייט מיט קאָנסעקוטיווע עלעמענטן אין עס אין קעסיידערדיק צייט. לאָמיר זען ווי, און דעמאָלט מיר וועלן צו יבערמאַכן די אויבן פּראָבלעם צו די אונטן פּראָבלעם:

לאָמיר רעכן אַ קייט = [3,4,5,6,7,8,9,10], און מיר מוזן צולייגן קסאָר אין די קייט צווישן ערשטער און לעצט עלעמענט.

זאל x זיין קיין גלייך נומער און y זיין די נומער ווייַטער צו x y = x + 1. מיר קענען לייכט פונאַנדערקלייַבן אַז קסאָר פון קס און 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 אָפּעראַציע אין אַן Array Leetcode לייזונג

קאַנווערטינג די פּראָבלעם אין קאָנסעקוטיווע קייט XOR

אין דעם אויבן פּראָבלעם מיר קענען רעדוצירן די ווייַטקייט צווישן יעדער עלעמענט פון 2 צו 1 אויב מיר רעכט יבעררוק ביטווייז יעדער עלעמענט דורך 1 (זעלביקער ווי דיוויידינג דורך 2). דורך דעם, מיר ווירקן בלויז די לעצטע ביסל פון די עלעמענטן. אַזוי מיר ערשטער קראָם די לעצטע ביסל פון אונדזער אַנס דורך פאלגענדע קאַסעס:

1. אויב אַלע די עלעמענטן אין מענגע איז מאָדנע און גאַנץ נומער פון עלעמענטן איז אויך מאָדנע, לאַסטביט = 1.
2. אלזא לאסטביט = 0.

נאָך די יבעררוק פון יעדער עלעמענט דורך 1 רעכט, אונדזער ריי איז:

אָנהייב / 2, אָנהייב / 2 +1, אָנהייב / 2 +2 ,. . . . , אָנהייב / 2 + (n-1).

ווו ערשטער = אָנהייב / 2 און לעצט = אָנהייב / 2 + (n-1).

איצט מיר קענען לייכט געפֿינען די קסאָר פון דעם קייט דורך דערגייונג ביטווייז קסאָר פון סוף עלעמענטן און אַלע אפילו-מאָדנע פּערז צווישן זיי אין קעסיידערדיק צייט.

נאָך דערגייונג קסאָר מיר האָבן צו ביטווייז לינקס יבעררוק דער רעזולטאַט דורך 1 צו געווינען די אָריגינעל שטעלע פון ​​ביטן אין אונדזער לעצט ענטפער. לעסאָף לייגן די לאַסטביט צו די רעזולטאַט און צוריקקומען עס.

ימפּלאַמענטיישאַן פֿאַר קסאָר אָפּעראַציע אין אַן Array Leetcode לייזונג

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

Java פּראָגראַם

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 אָפּעראַציע אין אַן Array Leetcode לייזונג

צייט קאַמפּלעקסיטי

אָ (1):  ווייַל מיר טאָן ניט גיין דורך אַלע די יסודות פון דעם מענגע, ניצן ביסל מאַניפּיאַליישאַן, מיר האָבן געטאן עס אין קעסיידערדיק צייט.

ספעיס קאַמפּלעקסיטי 

אָ (1):  דאָ אויך עקסטרע זכּרון איז קעסיידערדיק.