Company: Trilogy_10july
Difficulty: medium
Binary Search Failure Probability Problem Description Given the pseudocode below to find a target number i between l and r (both inclusive): while (l You are required to answer q queries, where in each query, you will be provided with values l and r . For each query, determine the following: What is the probability that the above code will fail to print "Found" when any value i (where l is chosen)? Express this probability as an integer where the fraction is P / Q and gcd(P, Q) = 1 . You should compute P * Q^-1 modulo 10^9 + 7 , where Q^-1 denotes the multiplicative inverse of Q modulo 10^9 + 7 . Examples Example 1: Input: A = [[2, 9]] Output: [500000004] Explanation: The numbers 2, 4, 6, 9 will result in the code failing to print "Found". Thus, the probability is 4 / 8 = 1 / 2, hence 1 * 2^-1 = 500000004. Example 2: Input: A = [[10, 10], [10, 12]] Output: [1, 666666672] Explanation: Since l and r are equal in the first query, the loop won't run, so the probability is 1. Only 11 will b