PROBLEM LINKS
DIFFICULTY
easy
PREREQUISITES
binary indexed tree, knowledge of binary base system and bitwise operations
PROBLEM
The question asks you to find the number of iterations required in a query operation on a binary indexed tree, aka Fenwick tree.
Let A be the array of integers of size n. In binary indexed tree, you store an additional array BIT as follows - BIT[i] denotes sum of A[j] + A[j + 1] | \dots + A[i], where j = i \, \& \, (i + 1).
The query operation for finding sum of A_0 + A_1 + \dots + A_i can be performed as given in the below pseudo code.
def query(i):
let sum = 0
while (i >= 0):
sum += BIT[i]
let j = i & (i + 1)
i = j - 1;
The query index i is given in a special way. Index i is obtained by concatenating three strings a, b, c in the following way - a + n * b + b. Here n is an integer, which denotes that string b is concatenated n times.
QUICK EXPLANATION
Number of iterations required in query for a fixed i will be total number of 1’s in the binary representation of i - number of 1’s in the suffix of i + 1. These quantities can be found easily with some simple logic.
EXPLANATION
Understanding the i \& (i + 1) operation
Let us first understand the operation i \& (i + 1). We enumerate first few values of it.
From first look, it seems that for i = 1, 3, 7 the values of j are all zeros. The numbers 1, 3, 7 contain only digit 1 in their binary representation. This is not a coincidence. If i contains all 1’s, then (i + 1) will be 1 following by zeros. Now, you can see that i \, \& \, (i + 1) will be zero.
Let us understand what this operation does in general. Let binary representation of i be x11.. s.t. x is some binary number whose last bit is 0, and let number of trailing 1’s in i be y.
Binary represention of i + 1 will be (x + 1)00.., where number of zeros will be equal to number of trailing ones in zero (i.e. equal to y).
Now i \, \& \, (i + 1) will be (x \& (x + 1))000...
x 11..11
& (x + 1) 00..00
Note (x \& (x + 1)) will be x \& x = x, as x ends up with bit 0.
x 11..11
& x 00..00
= x 00..00
So, we get i \, \& \, (i + 1) = x00..00.
Understanding the operation (i \, \& \, (i + 1)) - 1
Now let us see what will be (i \, \& \, (i + 1)) - 1. It will be x00..00 - 1. It becomes (x - 1) 11..11.
So if i = (x - 1) 11..11, then value of i after next iteration will be (x - 1) 11..11
Finding number of iterations in a query
Let us see what happens when you go to x - 1 from number x, where x ends up zero. Let the x be y000 where y ends up 1. Then x - 1 will be (y - 1)111, i.e. the last 1 of x is reset to 0 and all the digits followed by this gets converted to 1’s.
Hence, in each iteration, the prefix of 1’s at the end stays the same. The last 1 bit in the remaining initial part gets converted to zero, follwed by all the digits equal to 1, i.e. the length of suffix of 1’s keeps on increasing till all the bits become equal to 1. After that the next value of i will be become -1.
Example:
So, we see that number of iterations required in query for a fixed i will be total number of 1’s in the binary representation of i - number of 1’s in the suffix of i + 1.
Solving the final problem
The final problem asks us to solve the question for i such that binary representation of i is obtained by concatenating a + n * b + b where a, b, c are binary strings.
Let s = a + n * b + c.
So we want to find total number of 1’s in s, length of suffix of 1’s in s for solving the problem.
Total number of 1’s in s will be cnt_a + n \cdot cnt_b + cnt_c where cnt_a, cnt_b, cnt_c denote the count of 1s in a, b, c respectively.
Length of suffix of 1’s can also be found as follows. Let suf_a, suf_b, suf_c denote the count of suffix of 1s in a, b, c respectively. Let suf_s denotes length of suffix of 1’s in s. We can find suf_s by the following pseudo code.
if suf_c < len_c, then suf_s = suf_c
else if suf_b < len_b, then suf_s = suf_b + suf_c
else suf_s = suf_a + n * suf_b + suf_c
Time complexity of the above solution will be \mathcal{O} (|a| + |b| + |c|).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.