PROBLEM LINKSDIFFICULTYeasy PREREQUISITESbinary indexed tree, knowledge of binary base system and bitwise operations PROBLEMThe 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.
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 EXPLANATIONNumber 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. EXPLANATIONUnderstanding the $i \& (i + 1)$ operationLet us first understand the operation $i \& (i + 1)$. We enumerate first few values of it. $$i = 0, \, 0 \, \& \, 1 = 0$$ $$i = 1, \, 1 \, \& \, 2 = 01 \, \& \, 10 = 00 = 0$$ $$i = 2, \, 2 \, \& \, 3 = 10 \, \& \, 11 = 10 = 2$$ $$i = 3, \, 3 \, \& \, 4 = 011 \, \& \, 100 = 000 = 0$$ $$i = 4, \, 4 \, \& \, 5 = 100 \, \& \, 101 = 100 = 4$$ $$i = 5, \, 5 \, \& \, 6 = 101 \, \& \, 110 = 100 = 4$$ $$i = 6, \, 6 \, \& \, 7 = 110 \, \& \, 111 = 110 = 6$$ $$i = 7, \, 7 \, \& \, 8 = 0111 \, \& \, 1000 = 0000 = 0$$ $$i = 8, \, 8 \, \& \, 9 = 1000 \, \& \, 1001 = 1000 = 8$$ 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$. $$i = x11..11$$ 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$). $$i + 1 = (x + 1)00..00$$ Now $i \, \& \, (i + 1)$ will be $(x \& (x + 1))000..$. $$i \, \& \, (i + 1) = $$ 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 queryLet 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: $$10010011$$ $$100\textbf{011}11$$ $$\textbf{0111}1111$$ $$\textbf{1}1111111$$ $$1 \text{ (iteration stops)}$$ 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 problemThe 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$ Time complexity of the above solution will be $\mathcal{O} (a + b + c)$. EDITORIALIST'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 19 Oct '16, 12:40

The setter's and the tester's solution aren't visible. Kindly look into it. Thank you. answered 19 Oct '16, 12:50

Please correct this line in problem statement Index ii is obtained by concatenating three strings a,b,c in the following way  a + n ∗ b + b . Here nn is an integer, which denotes that string bb is concatenated nn times. It should be a + n ∗ b + c answered 20 Oct '16, 23:15

@dpraveen @admin. Can you please explain this part of code in the editorialist solution
Why are we adding ans++ for cs==0 and 1 for all other cases?. Understood.. (tot 1s' in i)  (len of suffix 1s in i) +1 in the result expression. answered 24 Oct '16, 16:10
