Generating the largest decent number of given number of digits

Question

The Sherlock and the Beast challenge from HackerRank asks to generate the following number with \$n\$ digits for \$T\$ test cases:

A Decent Number has the following properties: its digits can only be 3's and/or 5's. The number of 3's it contains is divisible by 5. The number of 5's it contains is divisible by 3. If there are more than one such number, we pick the largest one.

My code may not be very optimal. Can you please point out which test cases it may fail, as I may have missed a few conditions? Any suggestions to optimize the code?

using namespace std;
#include<iostream>

int main() {
    int T;
    cin >> T;

    while (T >= 1) {
        int n, flag;
        cin >> n;
        int z = n;

        if(n%5==0){
            for(int r=1;r<=n;r++){
                cout<<"3";
            }cout<<"\n";
        }

        else if(n%5!=0){
        for (int i = 3; i <= n; i += 3) {
            if ((z - i) % 5 == 0) {
                flag = i;
                break;
            }
        }

        if (flag == 0|| (n-flag)%5!=0) {
            cout << "-1"<<"\n";
        }

        else {
            for (int x = 1; x <= flag; x++) {
                cout << "5";
            }
            for (int y = 1; y <= (n - flag); y++) {
                cout << "3";
            }
            cout<<"\n";
        }
        }
        T--;
    }
}

Answer 1

Since you're asking where the code is failing:

Your logic is flawed for at least the case n % 5 == 0 in which case you assume the whole number must always be made of 3's but that is wrong since for example for n = 15 the number consisting of all 5's would be larger and still fulfill the requirements.

Also your code invokes undefined behaviour since flag might be used before it is initialized in the case n % 5 == 0.

Ultimately what you are looking for is a solution to:

3 * f + 5 * t = n

where f is the number of 5's and t is the number of 3's and n is the known length.

One simple way to solve this is to transform it into:

f = n/3 - 5/3 * t

Now all you need to do is to check if there is a solution for t with 0 <= t <= n where f is a whole number which ultimately boils down to finding the smallest t where

n % 3 == (5 * t) % 3

So you have the three cases. Together with the knowledge that 5 % 3 == 2 we can deduce:

1. n % 3 == 0: (5 * t) % 3 == 0 for t = 0, 3, 6, 9, 12, 15, 18
2. n % 3 == 1: (5 * t) % 3 == 1 for t = 2, 5, 8, 11, 14, 17, 20
3. n % 3 == 2: (5 * t) % 3 == 1 for t = 1, 4, 7, 10, 13, 16, 19

Since we're interested in the smallest t (so the resulting number has the maximum number of 5's and is therefor the largest matching one) this leaves you with roughly this pseudo-code algorithm

switch (n % 3):
    case 0: t = 0;
    case 1: t = 2;
    case 2: t = 1;

if (5 * t <= n):
    print "5".repeat(n - 5 * t) + "3".repeat(5 * t) 
else
    print "-1"