HackerRank Number Theory – Chandrima and XOR

Challenge: Chandrima and XOR

Subdomeniu: Number Theory (number-theory)

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464744480

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/chandrima-and-xor/problem

Cerinta

Chandrima likes the XOR operation very much and keeps finding and solving related problems. One day she comes across a problem and gets stuck on it, which makes her sad. You being her friend decide to help her out by writing a code for the same. 

Consider a list of all natural numbers. Now you remove all numbers whose binary representation has at least two consecutive $1$ bits, from the list, hence generating a new list having elements $1,2,4,5,8,...$ and so on. Now you are given $N$ numbers from this newly generated list. You have to find the XOR of these numbers.

**Input Format**  
The first line has an integer $N$, denoting the number of integers in list $A$.  
The next line contains $N$ space-separated integers. $A_i$ represents the $A_i^{\text{th}}$ number of the generated list. Since the answer can be very large, print the answer modulo $(10^9+7)$.

**Output Format**  
Just print one line containing the final answer.  


**Constraints**  
$1 \le N \le 5\cdot 10^5$  
$1 \le A_i \le 10^{18}$

**Sample Input 1**  

    3
    1 2 3

**Sample Output 1**  

    7

**Sample Input 2**  

    3
    1 3 4

**Sample Output 2**  

    0

**Explanation**  

*Sample 1:*  
The values to be considered are $1,2,4$, and the answer is $1\oplus2\oplus4 = 7$.

*Sample 2:*  
The values to be considered are $1,4,5$, and the answer is $1\oplus4\oplus5 = 0$.

Cod sursa

# The XOR is simple enough. The trick is that they haven't given us the
# numbers to XOR, but their position in the list. To find the actual
# numbers, determine the number of numbers up to N bits long in the list.
# Count 0, since we can add any new bit to zero.
# Then there are 2 numbers with up to 1 bit, 3 with up to 2 bits, etc.
# To add the numbers with N bits, add the number of numbers with N-2 bits
# or less to the previous total (the numbers for N-1 bits).
# The result is the fibonacci sequence, since I just keep adding the last
# two numbers. And so the number I want is the Zeckendorf representation
# of the given index, reinterpreted as binary (repeatedly subtracting the
# largest Fibonacci number available from the index)
#
# I've got one case here that is failing, probably just barely failing the time limit.
# Let's try precalculating the powers as the small speedup needed.

def zeck(n):
    res = 0
    for i in range(f - 1, -1, -1):
        if n >= fib[i]:
            n -= fib[i]
            res += p2[i]
    return res

n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
    fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
    p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
    sol = sol ^ zeck(nums[j])
print(sol % modulus)