Minimum Digit Sum 2 Solution September Challenge 2021

Minimum Digit Sum 2 Solution

This problem is similar to the problem “MNDIGSUM”. The only differences are in the constraints and in the input format. In this problem the range for the base B is [2,R], the value of n can be upto 1012 and the total number of queries is at most 300. The differences are described in bold.

Let f(n,B) be the sum of digits of the integer n when written in base B. Given Q queries, each consisting of two integers n and r. Find the value of B corresponding to which f(n,B) is minimum for all 2≤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 two space separated integers n and r respectively.

Output Format

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

Constraints

  • 1≤Q≤300
  • 2≤n≤1012
  • 2≤r≤1012

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 “MNDIGSUM” (also worth 50 points) which is very similar to this problem, but has slightly different constraints.

Sample Input 1

3
216 7
256 4
31 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: Minimum Digit Sum 2 Solution in C

#include <stdio.h>
#include<limits.h>
 int main() {
	 int q;
	scanf("%d",&q);
	while(q--)
	{
	   long long  int n,r,l=2;
	   scanf("%lld %lld",&n,&r);
	    long long int min=INT_MAX;
	    long long int b;
	   long long  int w;
	     if(r>n )
	     {
	        printf("%lld\n",n);
	     }
	      if(n>=l && n<=r)
	     {
	     printf("%lld\n",n);
	     
	     }
	     else
	     {
	    for(long long int i=i;i<r;i++)
	    {
	        long long int p=n,sum=0;
	       while(p>0)
	       {
	           sum+=(p%i);
	           p/=i;
	          if(sum>min)
	           break;
	           
	       }
	       
	      
	        if(min>sum)
	        {
	        min=sum;
	        b=i;
	      
	        }
	        if(min==1)
	        break;
	    }
	        
	  printf("%lld\n",b);
	    
	}
	}
	return 0;
}

Program C++: Minimum Digit Sum 2 Solution in C++

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define min(a,b) ((a)<(b)?(a):(b))
int f(int x,int b) {
	int ans=0;
	while(x) ans+=x%b,x/=b;
	return ans;
}
int Ans;
signed main() {
	int T,n,a,b,i,now,ansb,ans;
	int t1,t2;
	scanf("%lld",&T);
	while(T--) {
		ans=0x7fffffff;
		scanf("%lld%lld",&n,&b);a=2;Ans=min(b,sqrt(n));
		for(i=a; i<=Ans; i++) {
			if(n%i>ans)continue;now=f(n,i);
			if(ans>now) ans=now,ansb=i;
		}
		if(b>Ans) {
			if(f(n,b)<ans) ans=f(n,b),ansb=b;
			for(i=1; i<=45; i++) {
				t1=n/i;if(t1<a)continue;if(t1>b) t1=b;t2=n-i*t1;if(t2>=t1) continue;
				if(ans>i+t2) ans=i+t2,ansb=t1;
			}
		}
		printf("%lld\n",ansb);
	}
	return 0;
}

Program Java: Minimum Digit Sum 2 Solution in Java

import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc =new Scanner(System.in);
		int t=sc.nextInt();
		for(int i=0;i<t;i++)
		{
		    long n=sc.nextLong();
		    long r=sc.nextLong();
		    long min=n,out=0,k=0;
            long out1=ReturnPrimeProduct(n);
		     System.out.println(out1);
		}
	}
	static int f(int n,int b)
	   {   
	       int sum=0;
	       while(n>0)
	       {
	           sum+=n%b;
	           n/=b;
	       }
	       return sum;
	   }
	   static long ReturnPrimeProduct(long n)
	   {
	       long P=1;
	       boolean f=false;
	       while(n%2==0){
	           f=true;
	           n/=2;
	       }
	       if(f)
	       {
	           P*=2;
	           f=false;
	       }
	       for(int i=3;i<=Math.sqrt(n);i++)
	       {
	           while(n%i==0){
    	           f=true;
    	           n/=i;
	            }
    	       if(f)
    	       {
    	           P*=i;
    	           f=false;
    	       }
	           
	       }
	       if(n>2)
	            P*=n;
	       return P;
	   }
	static long f(long n,long b)
	   {   
	       if(n==0)
	            return 0;
           return( f((n/b),b) + (n%b));
	   }
	   
}

Program Python: Minimum Digit Sum 2 Solution in Python

try:
    def ds(n):
        num_str = str(n)
        sum = 0
        for i in range(0, len(num_str)):
            sum += int(num_str[i])
        return sum
    
    for _ in range(int(input())):
        n,d = map(int,input().split())
        s = set()
        temp = n
        for i in range(500000):
            if temp<=9:
                if not temp in s:
                    s.add(temp)
                    temp = temp+d
                else:
                    break
            else:
                temp = ds(temp)
        s = sorted(s)
        k = s[0]
    
        q = []
        ans = 0
        q.append((n,1))
        while len(q) != 0:
            num = q[0][0]
            step = q[0][1]
            q.pop(0)
            if num is k:
                ans = step-1
                break
            q.append((num+d,step+1))
            q.append((ds(num),step+1))
    
        if d%2 == 0:
            print(ans//d)
        else:
            print(ans)
except:
    pass

September Long Challenge 2021 Solution

2 thoughts on “Minimum Digit Sum 2 Solution September Challenge 2021”

Leave a Comment

12 − ten =