×

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.

Understanding the $i \& (i + 1)$ operation

Let 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 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:

$$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 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|)$.

EDITORIALIST'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

2.5k53137170
accept rate: 20%

19.8k350498541

 0 The setter's and the tester's solution aren't visible. Kindly look into it. Thank you. answered 19 Oct '16, 12:50 87●2●6 accept rate: 0%
 0 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 1 accept rate: 0%
 0 @dpraveen @admin. Can you please explain this part of code in the editorialist solution if (cs == 0) ans++; else if (cs < strlen(c)) ans -= cs - 1; else if (bs < strlen(b)) ans -= cs + bs - 1; else ans -= cs + n * bs + as - 1;  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 3★shiva92 11●1 accept rate: 0%
 0 What is number of 1's in the suffix of i+1 ?? answered 23 Jul '17, 19:48 161●8 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,719
×3,770
×371
×63
×1

question asked: 19 Oct '16, 12:40

question was seen: 3,589 times

last updated: 23 Jul '17, 19:48