Minimize Digit Sum Solution | Codechef September long challenge 2021

                 September Challenge 2021 (Rated for Div 3)

                                    Scorable Problems for Division 3

Name	Code	Successful Submissions	Accuracy
Airline Restrictions	AIRLINE
Travel Pass	TRAVELPS
Shuffling Parities	SHUFFLIN
XOR Equal	PALINT
Minimize Digit Sum	MNDIGSUM
2-D Point Meeting	POINTMEE
Covaxin vs Covishield	COVAXIN
Treasure Hunt	TREHUNT
Minimum Digit Sum 2	MNDIGSM2

Codechef September long challenge 2021 | Minimize Digit Sum Solution

• Post published:September 4, 2021
• Post category:Coding
• Post comments:0 Comments

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

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

Input Format

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

Output Format

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

Constraints

• 1≤Q≤1031≤Q≤103
• 2≤n≤1092≤n≤109
• 2≤l≤r≤1092≤l≤r≤109

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 11: We have f(216,2)=f(216,3)=4f(216,2)=f(216,3)=4, f(216,4)=6f(216,4)=6, f(216,5)=8f(216,5)=8, f(216,6)=1f(216,6)=1 and finally f(216,7)=12f(216,7)=12. Clearly the minimum is obtained when B=6B=6.

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

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

“C++14 Solution” (Updated)

#include <bits/stdc++.h>

using namespace std;

class Test{

public:

int solve(){

int q, n, l, r, enterInt, sum, min, sum2;

cin >> q;

for (int i = 0; i < q; i++) {

cin >> n >> l >> r;

if (n >= l && n <= r) {

cout << n << "\n";

continue;

}

if (n < l) {

cout << l << "\n";

continue;

}

sum2 = INT_MAX;

min = 0;

while (l < r && n / r < r) {

int temp1 = n / r, temp2 = n % r;

if (sum2 > temp1 + temp2) {

sum2 = temp1 + temp2;

min = r;

}

r = n / (temp1 + 1);

}

while (l <= r) {

enterInt = n;

sum = 0;

for (;;) {

if (enterInt < l) {

sum += enterInt;

if (sum < sum2) {

min = l;

sum2 = sum;

}

break;

}

sum += enterInt % l;

enterInt /= l;

if (sum >= sum2)

break;

}

l++;

}

cout << min << "\n";

}

}

};

int main() {

ios::sync_with_stdio(0);

cin.tie(0); cout.tie(0);

Test tt;

tt.solve();

return 0;

}