CareerCup

You are given positive integers N and D. You may perform operations of the following two types:

add D to N, i.e. change N to N+D
change N to digitsum(N)
Here, digitsum(x) is the sum of decimal digits of x. For example, digitsum(123)=1+2+3=6, digitsum(100)=1+0+0=1, digitsum(365)=3+6+5=14.

You may perform any number of operations (including zero) in any order. Please find the minimum obtainable value of N and the minimum number of operations required to obtain this value.


this is my code I am getting the wrong answer in some test cases please let me know where I am wrong.




#include<iostream>
#include<queue>
using namespace std;
void check(long long int a, long long int &b, long long int &c, long long int d)
{
if(a<b)
{
b = a;
c = d;
}
}
int digitSum(long long int a)
{
int num = 0;
while(a>0)
{
num += a%10;
a = a/10;
}
return num;
}
void func(int N, int D, long long int &minElement, long long int &minTrial)
{
queue<long long int> q;
q.push(N);
if(N==1)
{
minElement = 1;
minTrial = 0;
}
long long int countNodes = q.size();
long long int level = 1;
int cnt = 1;
while(!q.empty())
{
countNodes = q.size();
while(countNodes>0)
{
long long int temp = q.front();
q.pop();
long long int first = temp+D;
check(first,minElement,minTrial,level);
if(minElement == 1)
{
return;
}
q.push(first);
long long second = digitSum(temp);
check(second,minElement,minTrial,level);

if(minElement == 1)
{
return;
}
q.push(second);
countNodes--;
cnt++;
if(cnt>1000000)
{
break;
}
}
if(cnt>1000000)
{
break;
}
level++;
}
}
int main()
{
long long int t = 1;
cin>>t;
while(t--)
{
long long int N, D;
cin>>N>>D;
long long int minElement = 1e18, minTrial = 1e18;
func(N,D,minElement, minTrial);
cout<<minElement<<" "<<minTrial<<endl;
}
return 0;
}