Medium Search Techniques > Binary Search/Bisection

Let's denote, **SOD( X ) = Sum of Digits of X.** You will given an array with **N** integers and you have to perform **Q** queries. In each query, you have to find the maximum value of **SOD** of array elements between range **L** to **R** and the index for which the maximum **SOD** exits. More preciously, you have to find **MaxSOD( L, R ) = max( SOD( ar[l], ar[l+1], ar[...], ar[r-1], ar[r] ) )** and the index for which **MaxSOD( L, R ) = SOD( ar[index] )**. If there are multiple indexes, print the smallest one. Input: ------ Input starts with an integer **T (1 ≤ T ≤ 3)**, denoting the number of test cases. Each case contains two integer **N (1 ≤ N ≤ 100000)**, **Q (1 ≤ Q ≤ 300000)** denoting the number of elements of array and number of queris respectively. The next line will contain **N** integers separated by spaces, denoting the elements of the array and the number of queries respectfully. Each of these integers will be less than or equal to **1000000**. The next **Q** lines will contains two integers **L** and **R (1 ≤ L ≤ R ≤ N)**. Output: ------- For each test case, in the first line, print the test case number formatted as **"Case #tc:"** without quots. Where **tc** denotes the test case number. Perform each query as described above and print the desired answers in next **Q** lines. Sample Input ------------ 1 4 2 7 7 6 3 1 3 3 4 Sample Output ------------- Case #1: 7 1 6 3

Emrul Chowdhury