Sparse table and GCD

Questions 1 to 5 of 8

1. 1. What does this program print, one number per line? ``python def gcd(a, b): while b != 0: a, b = b, a % b return a print(gcd(48, 36)) print(gcd(12, -18)) print(-7 % 3) print(7 % -3) ``

   12, -6, 2, -212, 6, -1, 112, -6, -1, 212, 6, 2, -2
2. 2. What does this program print, one value per line? ``python a = [3, 9, 4, 4, 0] level1 = [min(a[i], a[i + 1]) for i in range(len(a) - 1)] print(level1) print((7).bit_length() - 1) print((8).bit_length() - 1) ``

   [3, 9, 4, 4] 2 3[3, 4, 4, 0] 2 3[3, 4, 4, 0] 3 3[3, 4, 4, 0] 2 2
3. 3. Which statements about the sparse table in this lesson are true? Pick all that apply.

   Pick every answer that is true.

   Each level k is built from level k-1 by taking the minimum of two neighbouring blocksA query on a range of length 5 reads two stored blocks of length 4The table stores an answer for every possible range, so it holds about n * n / 2 valuesAfter a[4] changes, the table must be rebuilt before a new query is correctRange sum queries are correct with the same two-block trick, because the blocks overlap
4. 4. A sparse table is used to answer range sums with the same overlapping-blocks query it uses for minimum. True or false, with the reason?

   False, because counting the overlapped items twice changes the sum, while min(x, x) is still xTrue, because the overlapped items are counted twice, and that does not change a sum
5. 5. For an array of 100000 numbers, how many levels does a sparse table have, counting level 0 up to the top level?

   16100000617