In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 7th
(this exercise will still be available for submission after that deadline, but without counting towards your grade)
[to understand the context of this problem, you should read the class #08 exercise sheet]
In this problem you should submit a function as described. Inside the function do not print anything that was not asked!
Daenerys Targaryen, the Mother of Dragons, has tasked you with a perilous challenge. She wants to know how many occurrences of the letter 'A' appear between two given positions of the White Rabbit game. She will only spare you from the wrath of her dragons if you can solve this puzzle efficiently. Failure to do so will result in her commanding Drogon to unleash Dracarys upon you.
The first lines of the game are:
A AB ABA ABAAB ABAABABA ABAABABAABAAB ABAABABAABAABABAABABA
Write a function count_range(a,b) that given two integers a and b, returns the number of 'A's that appear between positions [a,b] (inclusive) on the word game.
For instance, count_range(3,10) should return 5:
ABAABABAABAABABAABABA
And count_range(2,19) should return 11:
ABAABABAABAABABAABABA
The following limits are guaranteed in all the test cases that will be given to your program:
1 ≤ a ≤ b ≤ 1030 | positions of the range |
NOTE: the limits are really high and you must have an efficient solution that can compute this very quickly. Your program will need to be able to answer around five hundred queries in less than one second.
Example Function Calls | Example Output |
print(count_range(3,10)) print(count_range(2,19)) print(count_range(42,297)) |
5 11 159 |