# 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 ("Sherlock and The Beast"):

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

1. Only 3 and 5 as its digits.
2. Number of times 3 appears is divisible by 5.
3. Number of times 5 appears is divisible by 3.
4. Input should be the number of digits (N) where 1 <= N <= 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>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>=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;
}

• I'm doing the same problem. I know there's a lot of stuff on the "math" side I'm not getting. However, the biggest improvement I found was starting with the largest number (eg. if N is 6, the largest possible decent number would be 555555) and working downwards. I'm not sure if this is your program for checking if something is decent, or also looping. – NotAnAmbiTurner Jun 4 '16 at 2:00

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.

• Thanks a lot, I am still stewing through this but I believe I am about to learn something valuable ... ;-) – rolfl Oct 24 '14 at 18:16

Your algorithm is fast (vnp has an interesting solution too), but your implementation is a bit messy.

First, some nit-picks:

• why the continue? The previous block returns, and the loop immediately happens, so the else/continue is completely redundant....

        return 0;
}
else
continue;

• The entire first if-condition is a special case of the for-loop, and can be removed entirely.

• the for loop can have the max_div declared inside the loop too.

• I woul dhave a function that just returns the max_div for an input value (or -1 if not possible), and then handle it outside. Your function is doing too much (calculating and printing).

Consider this function:

int highFives(int num) {

for (int max_div = num / 3; max_div >= 0; max_div--) {
num_of_5s = max_div * 3;
num_of_3s = num - num_of_5s;
if (num_of_3s % 5 == 0 ) {
return num_of_5s;
}
}
return -1;
}


You can then call this function with:

int num5s = highFive(num);
if (num5s >= 0)
{
print(num5s, num - num5s);
}

• Even though i learned programming quite some time back, i had not practiced much and hence you may see some mess in my code. I liked your suggestions. Will try to adopt. But waiting for the clarification of your comment for "@vnp's" answer. – bluefoggy Oct 24 '14 at 18:02