# S06E06 - Editorial

Setter: Kanhaiya Mohan
Tester: Nishant Shah
Editorialist: Abhishek Ghosh

Easy

None

# PROBLEM

Given a number N. You need to maximize the product of its digits by incrementing them at most K times.

# EXPLANATION

Observation: Incrementing smaller numbers contribute more to the overall product as compared to incrementing larger numbers.

Proof

A product of 2 numbers can be laid out on a 2-dimensional grid. E.g. 3 * 5 can be represented as

Incrementing the larger number i.e. 5 will include region 1 and increase the product by 3.

Whereas, incrementing the smaller number i.e. 3 will include region 2 and increase the product by 5.

The same idea can be extended to any product of multiple numbers.

So, we increment the digits in the increasing order of their value until either we exhaust all our operations or reach the maximum possible number.

# IMPLEMENTATION

In each operation we take the current minimum digit (If it is not equal to 9) ​and increase that by 1.

→ Example:

Consider the sample test case with N=2221 and K=3.

In the first iteration, there is no digit less than 1 in the array.

In the second iteration, 22212222 and K=2.

In the third iteration, 22223322 and K=0 (No more moves left).

So, the maximum product = 3 * 3 * 2 * 2 = 36.

Time complexity - O(9*K), where K is the number of digits in N

# SOLUTIONS

Setter's Solution
``````#include <bits/stdc++.h>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int t;
cin >> t;
while(t--){
string s;
int k;
cin >> s >> k;
for(int i = 1; i <= 9; i++){
for(int j = 0; j < s.length(); j++){
if(s[j] < char('0' + i)){
if(k == 0){
break;
}
s[j] = '0' + i;
k--;
}
}
}
int ans = 1;
for(char j : s){
ans *= (j - '0');
}
cout << ans << '\n';
}

return 0;
}
``````
6 Likes

After getting input n and k as int, I implemented the following logic. but it’s not working. Can someone give any explain why?
a = list(str(n))
a = [int(i) for i in a]
hq.heapify(a)
while k>0:
# print(a)
x = hq.heappop(a)
if x == 9:
break
x = x + 1
hq.heappush(a, x)
# print(a)
k-=1
ans = 1
for i in range(len(a)):
ans *= a[i]
print(ans)

1 Like

The code is in python

You forget to push 9 back into the heap before break.

1 Like

Why this code shows WA on 2nd and third test case
https://www.codechef.com/viewsolution/54543180

#include
using namespace std;

int main()
{
int ts;
cin >> ts;
long long int N, K;
long long int size;
long long int maxIndex;
long long int maxProduct;
long long int product;
while (ts)
{
cin >> N >> K;
size = 0;
maxProduct = 1;
long long int A[7] = {1};
while (N)
{
A[size] = N % 10;
N = N / 10;
size++;
}

``````for (long long int i = 0; i < size; i++)
{
if (A[i] == 0)
{
A[i] = 1;
K--;
}
}
for (long long int i = 0; i < size; i++)
{
maxProduct = maxProduct * A[i];
}
for (long long int j = 1; j <= K; j++)
{
maxIndex = -1;
for (long long int i = 0; i < size; i++)
{
if (A[i] != 9)
{
product = 1;
for (long long int m = 0; m < size; m++)
{
if (m == i && A[m] != 9)
product = product * (A[m] + 1);
else
product = product * A[m];
}
if (product > maxProduct)
{

maxProduct = product;
maxIndex = i;
}
}
}
if(maxIndex!=-1)
A[maxIndex]++;
}

cout << maxProduct << endl;

ts--;
``````

}
return 0;
}

After getting input n and k as int, I implemented the following logic. but it’s not working. Can someone give any explain why? Means it is Accepted for 1 subtask but other two giving WA.

1
13 4

Correct: 16

2
0 0
20 0

1
2

Correct:
0
0

1 Like

Can anyone tell me why my code is giving WA? Thanks in advanced.
https://www.codechef.com/viewsolution/54513043

/* – author: Devansh_0007 (CF) – /
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define debug(x) cout << #x <<" " << x << endl;
#define endl “\n”
#define pb push_back
#define vi vector
#define F first
#define S second
#define sp " "
#define vll vector
#define vpii vector<pair<int , int>>
#define vpll vector<pair<ll , ll>>
#define pii pair<int , int>
#define vs vector
#define mii map<int , int>
#define mll map<ll , ll>
#define set_bits __builtin_popcountll
#define sz(n) (int)n.size()
#define all(n) n.begin(), n.end()
#define allr(n) n.rbegin(), n.rend()
#define for0(i, n) for (int i = 0; i < n; i++)
#define mem(a) memset(a, 0, sizeof(a));
double PI = 3.1415926536;
const ll inf = 1e17+7;
const int MOD = (1e9 + 7);
inline ll gcd(ll a, ll b){ return b ? gcd(b, a % b) : a;}
inline ll lcm(ll a, ll b){ return a / gcd(a, b) * b; }
inline bool ispalindrome(string s){
int n=s.length(),i=0,j=n-1;
while(i <=j){
if(s[i] != s[j])return false;
i++,j–;
}
return true;
}
vector prime((ll)1e7 , 1);
inline void sieveOfEratosthene(){
ll n = 1e7;
prime[0] = prime[1] = 0;
for (int p = 2; p * p <= n; p++){
if (prime[p] == true){
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
for(ll i = 3 ; i < 1e7 ; i+=2){
if(prime[i]){
}
}
}
inline bool isprime(ll n){
if(n%2 == 0)
return false;
for(int i=3;i
i<=n;i+=2)
if(n%i == 0)
return false;
return true;
}
ll fastpow(ll x , ll n){
ll res = 1;
while(n > 0){
if(n%2){
res = x;
}
n = n/2;
x =x;
}
return res;
}
ll pow_mod(ll x, ull n, ll m = MOD ){
ll res=1;
x=x%m;
if (x==0) return 0;
while (n > 0){
if (n & 1) // n is odd
res = (res
x) % m;
n = n>>1; // n = n/2
x = (x
x) % m;
}
return res;
}
ll modInverse(ll a, ll m){
int g = gcd(a, m);
return pow_mod(a, m - 2, m);
}
void printbinary(int n){
for(int i = 10 ; i >= 0 ; i–){
cout<<((n >> i) & 1 );
}
}
void solve(){
string ss;
cin >> ss;
ll k , n = sz(ss);
cin >> k;
vll a(n);
for0(i,n){
a[i] = ss[i] - ‘0’;
}
sort(all(a));
ll ans = 1;
for(ll i = 0 ; i < n-1; i++){
while( (a[i] < a[i+1] ) && k > 0){
k–;
a[i]++;
}
}
while(k > 0){
bool f = 1;
ll mm = k;
for(int i = 0 ; i < n; i++ ){
if(a[i] != 9){
a[i]++;
k–;
}
if(k <= 0){
f = 0;
break;
}
}
if(!f || mm == k){
break;
}
}
for(int i = 0 ; i < n; i++ ){
ans = ans * a[i];
}
cout << ans;
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
sieveOfEratosthene();
cin >> t;
for(int i=1;i<=t;i++){
// cout<<“Case #”<<i<<": ";
solve();
cout<<endl;
}
return 0;
}

Why it got WA on test case 2

``````#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
int t;
cin >> t;
while(t--){
int n,k;
cin >> n >> k;
if(n<10) {
cout << n+k <<endl;
continue;
}
int temp=n,sum=1;
priority_queue<int,vector<int>,greater<int>> res;
while(temp!=0){
int rem=temp%10;
res.push(rem);
temp=temp/10;
}
while(k--){
int s=res.top();
res.pop();s+=1;
res.push(s);
}
while(!res.empty()){
int s=res.top();
sum=sum*s;
res.pop();
}
cout << sum <<endl;

}
return 0;
}
``````

Does anyone have an idea on why this is failing for 2nd and 3rd cases??
Thank-you!!

Thanks bhai

import numpy
t = int(input())
for i in range(t):
a,N = map(int,input().split())
a = str(a)

``````a = list(a)
count1 = 0
if(min(a) == 0):
if(a.count(0) > N):
print(0)
exit(1)
else:
while(count1<N):
a = list(map(int, a))
i = a.index(int(min(a)))
a[i] = int(a[i])+1
count1 = count1+1
a = list(map(int, a))
result1 = numpy.prod(a)
print(result1)
``````

#Could anyone point out what is going wrong in this code…

(https://www.codechef.com/viewsolution/54598971)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include <unordered_set>
#include <unordered_map>

//#include
using namespace std;

#define ln ‘\n’
#define ll long long
#define MOD 1000000007

void solve()
{
string n; ll k;
cin >> n >> k;
////////////////////////////////////////
map<char, ll> mp;
for(char c : n) {
mp[c]++;
}
while(k > 0) {
auto p = mp.begin();
if(p->first == 9) break;

``````    if(k >= p->second) {
k -= p->second;
mp[p->first + 1] += p->second;
mp.erase(p->first);
} else {
mp[p->first] -= k;
mp[p->first + 1] += k;
k = 0;
}
}

ll ans = 1;
for(auto p : mp) {
ans *= pow((ll)(p.first - '0'), p.second);
}

cout << ans << ln;
``````

}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

``````ll t = 1;

cin >> t;
while (t--)
solve();
return 0;
``````

}

#include<bits/stdc++.h>
using namespace std;// #define {}[]
const int N=1e6+10;

long long trees[N];
map<int,vector>mp;

int main(){
int n; cin>>n;
while(n–) {
int t,k; cin>>t>>k;
std::vector v;
while(t){
int k=t%10;
v.push_back(k);
t=t/10;
}
for (int i = 1; i <= k; ++i)
{
sort(v.begin(),v.end());
if (v[0]!=9)
{
v[0]=v[0]+1;
}

``````        }
int c=1;
for (int i = 0; i < v.size(); ++i)
{
c*=v[i];

}

cout<<c<<"\n";

}
return  0;
``````

}

is this good
?