CHEFLUCK - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

We want the lucky lucky number to be as small as possible. Thus, we want the number to have maximum number of 4’s placed in the beginning of the number. We can write N = 7Q + R, i.e, R = N mod 7.

If R = 0, count of 4 = 7Q and count of 7 = 0

If R = 1, count of 4 = 7*(Q-1) and count of 7 = 8 ( Thus we are removing some 4’s and placing some 7’s instead. We are trying to remove only the minumum required number of 4’s )

If R = 2, count of 4 = 7*(Q-2) and count of 7 = 16

If R = 3, count of 4 = 7*(Q-3) and count of 7 = 24

If R = 4, count of 4 = 7Q and count of 7 = 4

If R = 5, count of 4 = 7*(Q-1) and count of 7 = 12

If R = 6, count of 4 = 7*(Q-2) and count of 7 = 20

Whenever, count of 4 becomes negative, in any of the above cases, it is impossible to form a lucky lucky number.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

1 Like
2

I m not understanding how the equation 7*(Q-1) came for each vLue of R…can anyone please help??

3

I used Euler Phi to solve the problem. Well to be exact, I used a variation of “Highest Impossible Score”. More details here: http://zobayer.blogspot.com/2009/07/greatest-impossible-score-in-game.html

4

#include<stdio.h>
int main(){
int t,r;
long n;
scanf("%d",&t);
while(t–>0){
scanf("%ld",&n);
r=n%7;
if(r==0&&n>=7) printf("%ld\n",n);
else if(r==1&&n>=8) printf("%ld\n",n-8);
else if(r==2&&n>=16) printf("%ld\n",n-16);
else if(r==3&&n>=24) printf("%ld\n",n-24);
else if(r==4&&n>3) printf("%ld\n",n-4);
else if(r==5&&n>4) printf("%ld\n",n-12);
else if(r==6&&n>19) printf("%ld\n",n-20);
else printf("%d\n",-1);
}
return 0;
}

5

How are we calculating count of 7 on each turn? Can somebody explain

1 Like
6

Alternative approach to it is as follows:
Suppose y is the no of digits 7. it can be expressed as y=4k (Y must be divisible by 4) ans is going to be
N-y. Now, (N-y)%7 = 0 as no. digits (4) to be divisible by 7.
=>(N-4k)%7=0 =>(N%7)-[(4%7) * (k%7)]%7=0
=>(N%7)=[4*(k%7)]%7
=>on comparing ,List of LHS values=[0,1,2,3,4,5,6] and corresponding RHS values of k=[0,2,4,6,1,3,5]. as can be seen K value is obtained from N%7 as [2*(N%7)]%7.
once you find k you get no. of digits (7) as 4k .you can then subtract this value from N.
If this value is less than 0 ans is -1 else ans=N-4k.
Here is the link to my solution.My JAVA SOLUTION

1 Like
7

Well i finally figured it out. Tester’s solution is helpful once you try to solve with pen and paper :wink:
Although i cant seem to understand why submissions of other users are not available.

8

I am having a small doubt.
To be lucky lucky number, a number should only contain only 4 and 7.
it was not 4 or 7.
so if n = 8 , how 8(44444444) can be the correct answer if it doesn’t contain 7.
Explain please!.

9

A solution with O(n) complexity—>(for test cases only)
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t–){
int n; cin>>n;
if(n%7==0)
cout<<n<<endl;
else{
int rem7 = n%7;
int rem4=rem7%4;
if(rem4){
int temp=rem4*7+rem4+(rem7/4)*4;
if(n-temp<0)
cout<<-1<<endl;
else{
cout<<n-temp<<endl;
}
}
else{
cout<<(n/7)*7<<endl;
}
}
}
return 0;
}