minimize digitsum


Forum Post 0 Answers minimize digitsum

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

- ceaser October 19, 2018 | Flag |






Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More