Problem of The Day 4 January — Lucky Numbers

Lucky Numbers

Leonardo thinks 4 and 7 are lucky digits! He defines a number as lucky if it can be represented as the sum of one or more of these lucky digits. For example, he considers the following numbers to be lucky:

You are given q queries, where each query consists of a long integer n denoting . For each query, print Yes on a new line if is a lucky number; otherwise, print No.

Input Format

The first line contains an integer denoting q.
Each of the q subsequent lines contains a long integer describing the value of n for a query.

Constraints

• 1 ≤ q ≤ 100
• 1 ≤ n ≤ 1016

Subtasks

• 1 ≤ n ≤ 1016 for 60% of the maximum score

Output Format

For each query, print Yes on a new line if is a lucky number; otherwise, print No.

Sample Input

4
1
4
11
17

Sample Output

No
Yes
Yes
No

Explanation

We perform the following q=4 queries:

1. n = 1 can’t be represented as a sum of 4’s and 7’s, so we print No on a new line.
2. n = 4 is a lucky digit (which means it’s also a lucky number), so we print Yes on a new line.
3. n = 1 can be represented as 4 + 7, so we print Yes on a new line.
4. n = 17 can’t be represented as a sum of 4’s and 7’s, so we print No on a new line.

Problem Link: Lucky Numbers

Solution will be posted tomorrow.

SOLUTION

You have to solve the equation 4*a + 7*b = N for a and b being integer.
So simply make the equation as (N — 7*b)%4 = (4*a)%4
Now R.H.S will be zero so we have to check if N-7*b ever become zero by increasing value of b
and if at any time N-7*b become negative we break the loop and print No.

CODE

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
int main()
{
    int q; cin>>q;
    while(q--) {
        ll n; cin>>n;
        ll b=0;
        while( n - b*7 >= 0)
        {
          if((n-b*7)%4==0 )   {
            cout<<"Yes"<<endl;
            break;
          }
          b++;
        }
        if((n-b*7) < 0 )
            cout<<"No"<<endl;
    }
}