We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Bit Manipulation
  4. Xor-sequence
  5. Discussions

Xor-sequence

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 133 Discussions, By:

votes

Please Login in order to post a comment

  • xshanz
    6 years ago+ 16 comments

    here is my O(1) solution

    #include <bits/stdc++.h>
    using namespace std;
    
    long long G(long long x){
        long long a = x % 8;
        if(a == 0 || a == 1) return x;
        if(a == 2 || a == 3) return 2;
        if(a == 4 || a == 5) return x+2;
        if(a == 6 || a == 7) return 0;
        return 0;
    }
    
    int main(){
        int q;
        cin >> q;
        while(q--){
            long long l, r, ans;
            cin >> l >> r;
            ans = G(r)^G(l-1);
            cout << ans << endl;
        }
        return 0;
    }
    
    88|
    Permalink
    View more Comments..
  • touchps
    6 years ago+ 1 comment

    Sometimes i feel reference solutions are more confusing and its better to design your own solution once you understand what's going on.

    16|
    Permalink
  • Cloverleaf
    6 years ago+ 4 comments

    My O(1) solution: From the index range [L, R], ignore all consecutive groups of 8 indices starting at the first multiple of 4. Then simply XOR the array values for the remaining indices. This is because each such group of 8 values will XOR to 0. The array value for an index i can be found using the following:

    i%4 == 0, then a[i] = i
    i%4 == 1, then a[i] = 1
    i%4 == 2, then a[i] = i+1
    i%4 == 3, then a[i] = 0

    Example: The first few array values go like this
    0 1 3 0 4 1 7 0 8 1 11 0 12 1 15 0 16 1 19 0 20 1 23 0

    For the above range, L = 5, R = 18, we skip the values in italics and just XOR the remaining i.e. 1, 7, 0, 16, 1, 19

    14|
    Permalink
    View more Comments..
  • EpsilonAlpha
    6 years ago+ 0 comments

    This has been one of my favorite questions on this site. It's all about the properties of XOR and finding patterns. Feels great after solving it.

    14|
    Permalink
  • Naisargee
    6 years ago+ 3 comments

    Have been strugling with this question for a while, and suddenly it hit me how simple it is. Try to extend given list of array and find pattern in it, that's all it requires.

    12|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature