Generating 'Decent' numbers While solving a problem from HackerRank, though it's an easy one, I wrote this big program. Not sure if recursion is applicable and hold good but to me it looked like it isn't. However when I run the program I see my code executed fairly well.
Here is the problem statement (&quot;Sherlock and The Beast&quot;):

Print the largest decent number.
A 'Decent' Number can have:

Only 3 and 5 as its digits.
Number of times 3 appears is divisible by 5.
Number of times 5 appears is divisible by 3.
Input should be the number of digits (N) where 1 &lt;= N &lt;= 100000.


For 10 such test cases if I have the inputs:
3647
8884 
1233
99999
130 
11111
3455
23454
123211
345

My code ran in 0.008688 seconds.
Is there any room for improvement?
int filldigits(num) {
    int max_div, num_of_5s, num_of_3s;
    if (num/3 == 0) {
        num_of_5s = num;
        print(num_of_5s, 0);
        return 0;
    }
    max_div = num/3;
    for (max_div; max_div&gt;0; max_div--) {
        num_of_5s = max_div * 3;
        num_of_3s = num - num_of_5s;
        if (num_of_3s % 5 == 0 ) {
            print(num_of_5s, num_of_3s);
            return 0;
        }
        else
            continue;
    }

    max_div = num/5;
    for (max_div; max_div&gt;=1; max_div--) {
        num_of_3s = max_div * 5;
        num_of_5s = num - num_of_3s;
        if (num_of_5s % 3 == 0)  {
            print(num_of_5s, num_of_3s);
            return 0; 
        }
        else
            continue;
    }
    return -1;
}
Is there any room for improvement?


Yes there is.

You have a Diophantine equation \$3x + 5y = N\$, (\$3x\$ and \$5y\$ being the number of occurrences of 5 and 3 respectively. A base solution is \$x = 2N, y = -N\$. All other solutions are in form of \$x = 2N - 5k, y = -N + 3k\$. That is, you just need to find \$k\$, which makes both numbers positive. Such as k = (N-1)/3 + 1 (if x becomes negative, there are no solutions).

Bottom line is that neither the loop nor the special cases are needed.

See Wikipedia article for details.

Edit: Paper exercise as requested:

Let N = 8. Base solution: x = 16, y = -8. (16*3 - 8*5 = 48 - 40 = 8).

k = (8 - 1)/3 + 1 = 3. x' = 16 - 3*5 = 1; y' = -8 + 3*3 = 1.

3*x' + 5*x' = 3 + 5 = 8.

Edit: another exercise.

Let N = 30. Base solution: x = 60, y = -30.

k = 29/3 + 1 = 10.

x' = 60 - 5*10 = 10; y' = -30 + 3*10 = 0, yielding the decent number of 30 occurrences of 5 and 0 of 3; just as requested.