DCP-498: Digit Sum Queries Back to All Problems

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


Problem Setter:

Emrul Chowdhury

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 2.50
C++ 2.50
C++14 2.50
C# 3.00
Go 3.00
Java 3.00
JavaScript 3.00
Objective-C 3.00
Perl 3.00
PHP 3.00
Python 3.00
Python3 3.00
Ruby 3.00
VB.Net 3.00

Problem Stats

66/306

Solve/Submission

Ranking

# User Language Timing
01 feodorv C 0.26s
02 emrul Cpp14 0.57s
03 jamil993 Cpp 0.80s
04 QuwsarOhi Cpp 0.96s
05 inam Cpp 0.97s
06 Rajan_sust Cpp14 0.97s
07 Masum_ice Cpp 0.97s
08 hamza133913 Cpp 1.00s
09 deder C 1.05s
10 Silent_Warrior Cpp 1.06s
11 Ramprosad Cpp 1.11s
12 AlaminJust Cpp 1.13s
13 SakibAlamin Cpp 1.13s
14 rayhan50001 Cpp14 1.14s
15 onucsecu Cpp14 1.15s
16 Bruteforcekid Cpp14 1.15s
17 mahade31 Cpp14 1.18s
18 Morshed_Raju Cpp 1.19s
19 pulak_ict_mbstu Cpp 1.20s
20 bu_hridoy Cpp 1.20s
21 Dragon_Curve Cpp 1.26s
22 clkjwdhc Cpp 1.26s
23 mh755628 Cpp 1.26s
24 sk23 Cpp 1.27s
25 Satkhira Cpp 1.27s
26 MRITuhin Cpp 1.27s
27 monir769 Cpp14 1.29s
28 ss1230 Cpp14 1.36s
29 mamun02inf Cpp14 1.38s
30 hmsayem Cpp14 1.40s
31 mhiceiuk Cpp 1.43s
32 Sarwar05 Cpp14 1.67s
33 FariD Cpp14 1.80s
34 yasirnabil534 Cpp 2.02s
35 fayedanik Cpp 2.09s
36 anik_JU Cpp 2.19s
37 tariqiitju Cpp14 2.21s
38 muradhossen Cpp 2.22s
39 int_elligent Cpp 2.26s
40 Khayrul_34 Cpp 2.31s
41 Frdhsn Cpp 2.34s
42 _GhOstMan_ Cpp 2.42s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support