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.
  1. Prepare
  2. Algorithms
  3. Bit Manipulation
  4. Xor-sequence
  5. Discussions

Xor-sequence

Sort by

recency

|

152 Discussions

|

  • yervand_markosy1
     + 1 comment

    The same modulus 8 solution in JavaScript/Node.js:

    function getXor(x) { let n = x % 8; if (n === 0 || n === 1) return x; if (n === 2 || n === 3) return 2; if (n === 4 || n === 5) return x + 2; return 0; }

    function xorSequence(l, r) { return BigInt(getXor(r)) ^ BigInt(getXor(l - 1)); }

  • tuan_lq121100
     + 0 comments

    There is a pattern of 4 consecutive elements in the array A, for example: A[0] -> A[3], and so on. The first number of the sequence = it's index, the 2nd number is 1, the third = index of the fourth and the fourth = 0. And, when you xor all 4 together, you always get 2. When you xor 2 sequences, you get 0, so it doesn't affect the remaining xor. Base on that, you can just find the effective xor, which are from left to the next start sequence index and from right back to the index after the last 8-element sequence.

    function getValue (idx) {
    let dp = 0n;
    let remain = idx % 4n;
    if(remain === 0n) dp = idx;
    if(remain === 1n) dp = 1n;
    if(remain === 2n) dp = idx+1n;
    if(remain === 3n) dp = 0n;   
    return dp;
}
function xorSequence(l, r) {
    [l, r] = [BigInt(l),BigInt(r)];
    if(l === r) return getValue(l);
    let output = getValue(l);
    let nextSequenceIdx = 4n*((l - l%4n)/4n + 1n);
    let leftoverIdxs  = (r-nextSequenceIdx+1n) % 8n;
    for(let i=l+1n; i<nextSequenceIdx;i++) {
        output = output^getValue(i);
    }
    for(let i=r; i>r-leftoverIdxs;i--) {
        output = output^getValue(i);
    }
    return output;
}

  • jmcparland
     + 0 comments

    Haskell

    So, if you look at the sequence of running XORs over the XORs, there's a pattern. I didn't give it much thought after that -- just implement the lookup function.

    module Main where

import Control.Monad (replicateM_)
import Data.Bits (xor)

lu :: Int -> Integer
lu 0 = 1
lu 1 = 2
lu 2 = 2
lu x = do
    let (q, r) = (x - 3) `quotRem` 8
        b = 8 * (fromIntegral q) + 6 :: Integer
     in [b, b + 1, 0, 0, b + 2, b + 3, 2, 2] !! r

solve :: Int -> Int -> Integer
solve 1 b = lu (b - 1)
solve a b = xor (lu (a - 2)) (lu (b - 1))

main :: IO ()
main = do
    cases <- readLn
    replicateM_ cases $ do
        [a, b] <- map read . words <$> getLine
        print $ solve a b

  • eduardocintrama1
     + 0 comments

    Hi there! Here is my Java solution for the challenge. If you'd like to discuss programming or any other topics, don't hesitate to reach out!

    https://github.com/eduardocintra/hacker-rank-solutions/blob/master/src/br/com/eduardocintra/medium/xorsequence/XorSequence.java

  • kumar_cse_576
     + 0 comments

    c++ optimal one

    long getXor(long x){
    int n=x%8;
    if(n==0||n==1)return x;
    if(n==2||n==3)return 2;
    if(n==4||n==5)return x+2;
    else return 0;
}

long xorSequence(long l, long r) {
return getXor(r)^getXor(l-1);
}