Minimum Digit Sum 2 Solution September Challenge 2021

Codechef 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 BB is [2,R][2,R], the value of nn can be upto 10121012 and the total number of queries is at most 300300. The differences are described in bold.

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 two integers nn and rr. Find the value of BB corresponding to which f(n,B)f(n,B) is minimum for all 2≤B≤r2≤B≤r. If there are multiple such values, you can print any of them

Also See: September Long Challenge 2021 Solutions

Input Format

  • The first line contains in single integer QQ, the number of queries
  • Each of the next QQ lines contain two space separated integers nn and rr respectively.

Output Format

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

Constraints

  • 1≤Q≤3001≤Q≤300
  • 2≤n≤10122≤n≤1012
  • 2≤r≤10122≤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 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=1)f(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.

Follow us on telegram for quick update an abundance of free knowledge: Click Here

Solution

Program 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++:

#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:

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:

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

Codechef Long Challenges

September Long Challenge 2021 Solution

August Long Challenge 2021 Solutions

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

Leave a Comment