Problem:
Ada gives John a positive integer . She challenges him to construct a new number (without leading zeros), that is a multiple of , by inserting exactly one digit (0
9
) anywhere in the given number . It is guaranteed that does not have any leading zeros.
As John prefers smaller numbers, he wants to construct the smallest such number possible. Can you help John?
Input
The first line of the input gives the number of test cases, . test cases follow.
Each test case has a single line containing a positive integer : the number Ada gives John.
Output
For each test case, output one line containing Case #:
, where is the test case number (starting from 1) and is the new number constructed by John. As mentioned earlier, cannot have leading zeros.
Limits
Memory limit: 1 GB.
.
Test Set 1
Time limit: 20 seconds.
.
Test Set 2
Time limit: 40 seconds.
For at most 10 cases:
.
For the remaining cases:
.
Sample
3
5
33
12121
Case #1: 45
Case #2: 333
Case #3: 121212
In Sample Case #1, there are only two numbers that can be constructed satisfying the divisibility constraint: and . John chooses the smaller number.
In Sample Case #2, is the only number possible.
In Sample Case #3, there are four possible options - , , and - out of which the smallest number is .
solution :
#include<bits/stdc++.h>
using namespace std ;
int sum_digits(string &n)
{
int len = n.length();
int sum = 0;
for(int i = 0 ; i < len ; i++)
{
sum = sum + (n[i]-48) ;
}
return sum ;
}
string convert(string &n)
{
string new_str;
int len = n.length();
int req_digit = 9 - sum_digits(n)%9;
if(req_digit == 9)
{
n.insert(1 , "0");
}
else
{
int flag = 0 ;
char s = req_digit+48;
for(int i =0 ; i < len ; i++)
{
if(s < n[i] && flag ==0 )
{
flag = 1;
n.insert(i,string(1,s));
break;
}
}
if(flag ==0 )
n.insert(len,string(1,s));
}
return n;
}
int main()
{
int t ;
cin >> t;
for(int i =1 ; i <= t ; i++)
{
string n ;
cin >> n ;
n = convert(n);
cout <<"Case #"<<i <<": " << n << "\n";
}
}
refrences :
how-to-insert-single-character-using insert() and string() in c++
Comments
Post a Comment