 # MNDIGSUM - Editorial

Author: Srikkanth R and Daanish Mahajan
Tester: Miten Shah
Editorialist: Aman Dwivedi

Easy-Medium

# PREREQUISITES:

Maths, Observation

# PROBLEM:

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

More formally, if n = \sum\limits_{i=0}^{\infty} a_i B^i where a_i is an integer in the range [0, B-1], then f(n, B) = \sum\limits_{i=0}^{\infty} a_i.

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 \leq B \leq r. If there are multiple such values, you can print any of them.

# EXPLANATION:

Our goal is to decide the base B which lies in the range [l, r] such that the sum of digits of the integer N when written in base B is minimum possible among all the choices of B.

The first basic observation that we can draw from the problem is that if we choose any Base B which is greater than \sqrt{N}, then there are only 2 non-zero digits in the base B representation. Hence, in this case, our number can be represented as:

a*x+b=N

Since our goal is to minimize the digit sum i.e. (a+b). Our x is greater than \sqrt{N}, hence our a will carry from \sqrt{N} -1 to 1. Hence for all the possible values of a we can simply found out the maximum value of x and then take out the minimum value of (a+b). We can easily found out the values of x and b in O(1) time.

For every possible value of a, we have:

x=\lfloor \frac{N}{a} \rfloor

and

b = N \hspace{0.1cm}mod \hspace{0.1cm}x

It takes us O(\sqrt{N}) time to traverse all the possible values of a.

Now we are only left with such bases whose values are less than \sqrt{N}. For that, we can easily brute force all the possible bases from l to \sqrt{N}.

Finally, we will output the bases B which gives us the minimum possible sum of digits among all the choices of B.

# TIME COMPLEXITY:

O(\sqrt{N} * C),

where C is constant for finding the base representation of number N.

# SOLUTIONS:

Author's
#include <bits/stdc++.h>

#define LL long long
using namespace std;

clock_t start = clock();

LL readInt(LL l, LL r, char endd) {
LL x = 0;
char ch = getchar();
bool first = true, neg = false;
while (true) {
if (ch == endd) {
break;
} else if (ch == '-') {
assert(first);
neg = true;
} else if (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + ch - '0';
} else {
assert(false);
}
first = false;
ch = getchar();
}
if (neg) x = -x;
if (x < l || x > r) {
cerr << l << " " << r << " " << x << " failed\n";
}
assert(l <= x && x <= r);
return x;
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert (g != -1);
if (g == endd) {
break;
}
++cnt;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
LL readIntSp(LL l, LL r) {
}
LL readIntLn(LL l, LL r) {
}
string readStringSp(int l, int r) {
}
string readStringLn(int l, int r) {
}

void solve() {
int i, have = -1, go = (int)1e9;
for (i=l;i*i<=n&&i<=r;++i) {
int ans = 0, m = n;
while (m > 0) {
ans += m % i;
m /= i;
}
if (ans < go) {
go = ans;
have = i;
}
}
for (;i<=r;++i) {
int nxt = min(r, n / (n / i));
int ans = n % nxt + n / nxt;
if (ans < go) {
go = ans;
have = nxt;
}
i = nxt + 1;
}
assert(have >= l && have <= r);
cout << have << '\n';
}

int main() {
while (T--) {
solve();
}
// End solution here
assert(getchar() == EOF);

cerr << fixed << setprecision(10);
cerr << "Time taken = " << (clock() - start) / ((double)CLOCKS_PER_SEC) << " s\n";
return 0;
}

Tester
#include <bits/stdc++.h>

#define LL long long
using namespace std;

clock_t start = clock();

LL readInt(LL l, LL r, char endd) {
LL x = 0;
char ch = getchar();
bool first = true, neg = false;
while (true) {
if (ch == endd) {
break;
} else if (ch == '-') {
assert(first);
neg = true;
} else if (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + ch - '0';
} else {
assert(false);
}
first = false;
ch = getchar();
}
if (neg) x = -x;
if (x < l || x > r) {
cerr << l << " " << r << " " << x << " failed\n";
}
assert(l <= x && x <= r);
return x;
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert (g != -1);
if (g == endd) {
break;
}
++cnt;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
LL readIntSp(LL l, LL r) {
}
LL readIntLn(LL l, LL r) {
}
string readStringSp(int l, int r) {
}
string readStringLn(int l, int r) {
}

void solve() {
int i, have = -1, go = (int)1e9;
for (i=l;i*i<=n&&i<=r;++i) {
int ans = 0, m = n;
while (m > 0) {
ans += m % i;
m /= i;
}
if (ans < go) {
go = ans;
have = i;
}
}
for (;i<=r;++i) {
int nxt = min(r, n / (n / i));
int ans = n % nxt + n / nxt;
if (ans < go) {
go = ans;
have = nxt;
}
i = nxt + 1;
}
assert(have >= l && have <= r);
cout << have << '\n';
}

int main() {
while (T--) {
solve();
}
// End solution here
assert(getchar() == EOF);

cerr << fixed << setprecision(10);
cerr << "Time taken = " << (clock() - start) / ((double)CLOCKS_PER_SEC) << " s\n";
return 0;
}

6 Likes

The values of x for which a*x+b=N for a given a and N lies in a range [1+(n/(a+1)),n/a]. For ex- If a=3 and N=35 then x can be anything between [1+(35/4),35/3] i.e [9,11]. Then , why are we taking only n/a?

2 Likes

Can someone please explain what is the significance of this line

int nxt = min(r, n / (n / i));

without it, theere shows TLE error

3 Likes

I had this approach and it worked for half test cases , for rest was getting TLE

 if(n<l && n<r) {
cout<<l<<endl;    // we could print low or high any answer will work
return;
}
else if(n>=l && n<=r) {
cout<<n<<endl;
return;
}
else {
// BRUTE FORCE
}


It’s a tech to speed up counting n / i for some i \in [l,r].

1 Like

Author’s solution will fail by RE on first test. It didn’t check the situation when i > n and leads to n / (n / i) is as the same as doing n / 0.

2 Likes

How to resolve this error, can you plz explain?

If there is no limit for B \in[l,r we can split the range into three sub-problem: [2, \sqrt(n) ] [\sqrt(n) +1,n] [n+1,...]
Let L,R represent the interval limits B
So we just need to let l \leq R be l \leq min(n,R).And remember when we pick up the r to calculate the answer,let it be \min(n,r,R).
Now the last is B > n,and from the editorial we know pick the biggest is the best way.So we just need to add the answer for B = R to check if it can reduce the value of the answer.
My code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
#define x first
#define y second

ll f(int x,int b)
{
ll res = 0;
while(x)
{
res += x % b;
x /= b;
}
return res;
}

int main()
{
int q;scanf("%d",&q);
while(q--)
{
int n,L,R;scanf("%d%d%d",&n,&L,&R);
int sq = sqrt(n);

pli res = {2e18,0};
for(int l = max(sq + 1,L),r = 0;l <= min(R,n);l = r + 1)
{
r = n / (n / l);
int b = min({r,R,n});
res = min(res,{n / b + n % b,b});
}

forn(b,L,min(sq,R))	res = min(res,{f(n,b),b});
res = min(res,{f(n,R),R});
printf("%d\n",res.y);
}
return 0;
}



Can anyone help, I’m tired getting wrong answer. What is the problem with this code and why I’m getting TLE in one of the subtask, despite of O(root(N))

using namespace std;

#define ll long long
#define mod 1000000007
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define PB push_back
#define MP make_pair

int DigitSum(ll n, ll b)
{
int a, sum = 0;

while (n > 0) {
a = n % b;
sum += a;
n = n / b;
}
return sum;
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin>>t;
while(t--)
{
ll n,l,r;
ll ans,mi=1e9;
cin>>n>>l>>r;
int nr = (int)sqrt(n);
FOR(i,l,nr+2)
{
int temp = DigitSum(n,i);
if(temp<mi) {mi = temp; ans =i;}

}

FOR(i,1,nr)
{
ll temp = n/i;
if(temp<l || temp>r) continue;
int digSum = n%temp+i;
if(digSum<mi) {mi = digSum; ans = temp;}
}

cout<<ans<<endl;
}
}`
1 Like

How come this first basic observation is concluded?.. Why not a 3 or more digit no. can have a smaller digit sum in this case? @cherry0697 @overjoy13 @starboy24 @mtnshh

For base greater than root n we always have 2 or less digits, for all else bases, we do it by brute force. But this problem was very ugly because it gave TLE for using an extra function, which is always encouraged to a programmer.

If we let B \geq \sqrt(n) + 1 and we can know that n / b < \sqrt(n) and same as n / b < b. So if you are doing such a B \geq \sqrt(n) + 1 and n will just spilt into two pieces: n / b and n % b. That’s why we can split the complexity into \sqrt(n) .

I had the same doubt. I think there’s some gap in the solution. It might even be correct inadvertently.

Can anybody explain me why we are taking x=floor(N/a)
x=(N-b)/a
x=N/a - b/a
why we are ignoring (-b/a)?

There are many good practices, like avoiding public members of a class and instead using accessor functions, or checking input parameters of a function for validity, which slow down execution.
The techniques needed for speed-sensitive competitions are somewhat different from real-world programming.

can u please explain this tech little more??? I am unable to understand what it is and how its working???

for continuous i \in[1,n] , the value of n / i looks like: 5 5 5 5 5 | 4 4 4 4|3 3| 2| 1111.It spreads like many continuous blocks. And the conclusion is for every i\in [1,n] the max j \geq i and n / i == n / j satisfy j = n / (n / i).
The complexity is O(\sqrt n) because the different value of n / i for i \in [1,n] at most 2 \sqrt n kinds.

1 Like

IIUC this is done to to reduce the sum of (a+b). For given a & n, if we take x as (n/a)-1 instead of n/a the value of a*x reduces by a, which has to be compensated by b. Since we want to reduce (a+b) and a is fixed we would like to take the least possible value of b.