Minimize Digit Sum Solution September Long Challenge 2021

Minimize Digit Sum Solution

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≤103
  • 2≤n≤109
  • 2≤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 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

Program C: Minimize Digit Sum Solution in C

#include <limits.h>
#include <stdio.h>
int main() {
    int q, n, l, r, inputNum, sum, min, sum2;
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d%d%d", &n, &l, &r);
        if (n < l) {
            printf("%d\n", l);
            continue;
        }
        if (n >= l && n <= r) {
            printf("%d\n", n);
            continue;
        }
        sum2 = INT_MAX;
        min = 0;
        /* optimize 2 digit case with high base */
        while (l < r && n / r < r) {
            int d1 = n / r;
            int d2 = n % r;
            if (sum2 > d1 + d2) {
                sum2 = d1 + d2;
                min = r;
            }
            /* skip all lower bases with same d1 */
            r = n / (d1 + 1);
        }
        while (l <= r) {
            inputNum = n;
            sum = 0;
            for (;;) {
                if (inputNum < l) {
                    sum += inputNum;
                    if (sum < sum2) {
                        min = l;
                        sum2 = sum;
                    }
                    break;
                }
                sum += inputNum % l;
                inputNum /= l;
                if (sum >= sum2)
                    break;
            }
            l++;
        }
        printf("%d\n", min);
    }
    return 0;
}

Program C++: Minimize Digit Sum Solution in C++

#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;
}

Program Java: Minimize Digit Sum Solution in Java

import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
    public static int func(int n,int b)
    {
        int sum=0;
        for(int i=n;i!=0;i/=b)
        {
            sum+=i%b;
        }
        return sum;
    }
	public static void main (String[] args) throws java.lang.Exception
	{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t=Integer.parseInt(br.readLine());
		while(t-->0)
		{
		    String [] s=br.readLine().split(" ");
		    int n=Integer.parseInt(s[0]);
		    int l=Integer.parseInt(s[1]);
		    int r=Integer.parseInt(s[2]);
		    int min=999999999,ind=-1;
		    if(r>n && l>=n)
		    {
		        System.out.println(l);
		        continue;
		    }
		    if(r>=n)
		    {
		        System.out.println(n);
		        continue;
		    }
		    while(l<r && n/r < r)
		    {
		        int t1=n/r;
		        int t2=n%r;
		        if(min>(t1+t2))
		        {
		        min=t1+t2;
		        ind=r;
		        }
		        r=n/(t1+1);
		    }
		    while(l<=r)
		    {
		        int e=n;
		        int sum=0;
		        for(;;)
		        {
		            if(e<l){
		                sum+=e;
		                if(sum<min)
		                {
		                    min=sum;
		                    ind=l;
		                }
		                break;
		            }
		            sum+=e%l;
		            e/=l;
		            if(sum>=min)
		            break;
		        }
		        l++;
		    }
		   
		    System.out.println(ind);
		}
	
	}
}

Program Python: Minimize Digit Sum Solution in Python

def ff(m,j):
    s=0
    while(m>0):
        s+=m%j
        m=m//j
    return s
t=int(input())
for item in range(t):
    n,l,r=map(int,input().split())
    s=0
    mn=n
    index=0
    if r>n:
        r=n
    for j in range(l,r+1):
        s=ff(n,j)
        if mn > s:
            mn=s
            index=j
    print(index)

September Long Challenge 2021 Solution

Leave a Comment

five × two =