12
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – NotAnAmbiTurner Jun 4 '16 at 2:00
6
\$\begingroup\$

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.

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

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);
}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – bluefoggy Oct 24 '14 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.