One Last Ride

An usual way to simplify problems that ask us to do something with a interval of integers [A,B] is to try to reduce it to solving for the easier interval [0,A]. In this case: A⊕(A+1)⊕…⊕(B−1)⊕B=(0⊕…⊕(B−1)⊕B)⊕(0⊕…(A−2)⊕(A−1)). (Where the numbers have already been converted to Letty notation and ⊕ is xor). We can find the xor sum results for [0,B]and then for [0,A−1] then xor them together to find the xor sum result for [A,B].

Bit by bit

The new problem is: Given a integer A, we want to find the xor sum of: f(0)⊕f(1)⊕…⊕f(A−1)⊕f(A) where f(x) turns the number into Letty notation. Since the operation is a binary xor, the result for each bit position is independent of the other bit positions.

We can try this simplification: Find the value of the i-th bit in f(0)⊕f(1)⊕…⊕f(A−1)⊕f(A). With this we can rebuild the number bit by bit. How many bits will we need? The largest Fibonacci number we will need is 806515533049393, which is the 72-th Fibonacci number (when we don’t count the zero). This means there will be at most 72 Fibonacci bits. Is the i-th bit 1? How to solve this question? We want to know if the i-th bit of f(0)⊕f(1)⊕…⊕f(A−1)⊕f(A) is 1. Just consider the number of times i-th bit position is 1 among f(0),f(1),…f(A). If an odd quantity of those numbers has 1 in that position, then the xor will be 1, else 0. Counting Letty numbers A way to rephrase that would be: Count how many numbers in f(0),f(1),…f(A) contain a 1 in the i-th bit position. Return the parity of this number. (If the count is even, return 0 else 1). This is the same as counting the number of ways to make a Letty number equivalent to a integer less than or equal to A such that the i-th position is 1. How can we tell if a binary number is valid? A binary number is valid if it is the Letty notation of a integer. The integer should be between 0 and A, inclusive. This requires us to understand Letty notation better. No consecutive 1s So let’s make some Letty numbers:

0: 00000

1: 00001

2: 00010

3: 00100

4: 00101

5: 01000

6: 01001

7: 01010

8: 10000

9: 10001

10: 10010

11: 10100

12: 10101

With some observation, the Letty representations never have two consecutive 1 bits. They are also lexicographically ordered. This is something experienced coders possibly already know because the Fibonacci base has been a mathematical delicacy for long and it has been used in various problems before.

There is more info about it in http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibrep.html#fibbase . Maybe you want a proof? Assume a Letty number begins with two consecutive bits. It means that its final sum will contain two Fibonacci numbers Fn−1 and Fn−2. However, their addition yields Fn=Fn−1+Fn−2, and this is a large Fibonacci number, the greedy algorithm described in the statement would pick Fn instead of Fn−1 and Fn−2. If the two consecutive 1 bits are not the first two bits, the situation is the same, except that the number was correctly re-generated by the greedy algorithm until meeting that position. The Letty numbers are ordered because lexicographically larger Letty numbers would always yield larger numbers when converted back to decimal. This requires a proof that when there are no two-consecutive Fi, Fi+1 in a sum of Fibonacci numbers, we cannot generate a larger Fibonacci number by adding them together. The important thing to conclude is that for a given integer A, we can find its f(A) representation in Fibonacci base and then what we need to count is the number of binary numbers less than or equal to f(A) such that there are no two consecutive 1 bits and the i-th bit is 1. We need to count this modulo 2 (The same as finding out if the count is even or odd)

The counting sub-problem The counting sub-problem is relatively simple for this problem slot. What we can do is to count the number of ways to fill the bits in a valid number. j A = 1001001001010 n = 1001000??? After we have filled all the bit positions greater than or equal to j, it is time to fill position j−1. We can pick 0 or 1 for this position.

There are times at which we cannot pick 1: The value we picked for bit j is 1, so we cannot put a consecutive 1 bit. All the previous values are equal to the values of A and the j−1 bit of A is 0. If we put 1 here, the number would become greater than A and that’s invalid. There is also a situation in which we cannot pick 0. When j−1=i. Keeping this in mind, we can make a dynamic programming solution using the following recurrence relation: f(j,less,last) where: j: Means that we have already picked the values for the bit positions greater than or equal to j less is 0 if and only if all the previous bit values are equal to those in A last is the value of the bit we put in bit position j.

Author’s Solution.- http://ideone.com/3FqA29