Minimize Digit Sum | CodeChef Solution

Hello coders, today we are going to solve Minimize Digit Sum CodeChef Solution whose Problem Code is MNDIGSUM.

Task

Let f (n, B) be the sum of digits of the integer n when written in base B.

Given Q queries, each consisting of three integers n, l and r. Find the value of B corresponding to which f (n, B) is minimum for all l ≤ B ≤ r. If there are multiple such values, you can print any of them.

Input Format

The first line contains in single integer Q, the number of queries
Each of the next Q lines contain three space separated integers n, l and r respectively.

Output Format

• For each query (n l r), print the value of base B which lies within [l ,r] such that f (n, B) is minimum.

Constraints

• 1 ≤ Q ≤ 10³
• 2 ≤ n ≤ 10⁹
• 2 ≤ l ≤ r ≤ 10⁹

Subtasks

Subtask #1 (50 points): original constraints

This problem is worth a total of 50 points and is meant to be complementary to the problem “MNDIGSM2” (also worth 50 points) which is very similar to this problem, but has slightly different constraints.

Sample Input 1

 3
 216 2 7
 256 2 4
 31 3 5

Sample Output 1

 6
 2
 5

Explanation

Test case 1: We have f (216, 2) = f (216, 3) = 4, f (216, 4) = 6, f (216, 5) = 8, f (216, 6) = 1 and finally f (216, 7) = 12. Clearly the minimum is obtained when B =6.

Test case 2: Note that f (256, 2) = f (256, 4) = 2, therefore both the answers 2 and 4 will be considered correct.

Test case 3: f (31, 3) = f (31, 5) = 3 and f (31, 4) = 7, therefore both the answers 3 and 5 will be considered correct.

Solution – Minimize Digit Sum

C++

Python

Java

Disclaimer: The above Problem (Minimize Digit Sum) is generated by CodeChef but the Solution is generated by CodingBroz. This tutorial is only for Educational and Learning Purpose.