Solving 'decent numbers' that follow specific division rules

Question

HackerRank Problem Statement

I have to find the largest 'decent number' having N digits. A decent number has the following properties:

• 3, 5, or both as its digits. No other digit is allowed.
• Number of times 3 appears is divisible by 5.
• Number of times 5 appears is divisible by 3.

My code works perfect, but, I am afraid it is far from efficient:

Input:

4 #number of test cases, i.e., the following 4 inputs
1
3
5
11

Output:

-1
555
33333
55555533333

My version of the solution:

T = int(input()) #number of test cases

def computePair(N):
    multiplesOf3 = [i for i in range(N+1) if i%3 == 0]
    if multiplesOf3 != [0]: #reversing a [0] results in a 'NoneType'
        multiplesOf3.reverse()
    multiplesOf5 = [i for i in range(N+1) if i%5 == 0]

    for i in multiplesOf3:
        for j in multiplesOf5:
            if (i+j) == N:
                return (i, j)
    return -1

for testCase in range(T):
    N = int(input()) #test case
    result = computePair(N)
    if result == -1:
        print(result) #If no such combination exists return '-1'
    else:
        print('5' * (result[0]) + '3' * (result[1]))

I assume my code has a time-complexity of \$O(n^2)\$; because of the two for loops. I want this to be more efficient in the order of \$O(n)\$ - linear.

This is a very generic question: also, do you have any resources to time-complexity best practices? I suck at it.

Answer 1

At the heart of your problem you are trying to solve a single linear Diophantine equation. Because 3 and 5 are coprime, their greatest common divisor is 1, and hence your equation, \$3a + 5b = n\$, will always have an integer solution. It is easy to check that \$a = 7n\$, \$b = -4n\$ is indeed one such solution. Of course you want both \$a\$ and \$b\$ to be positive, so if we take the more general solution to your equation, \$a = 7n - 5k\$, \$b = -4n + 3k\$, and impose \$b \ge 0\$, we get \$k = \lceil 4n / 3 \rceil\$.

Let's put this into a Python function:

def partition35(n):
    k = (4*n - 1) // 3 + 1  # rounded up int division
    a = 21*n - 15*k  # (7*n - 5*k)*3
    b = 15*k - 20*n  # (3*k - 4*n)*5
    return a, b

Notice that there is a single division performed. Division and modulo operations are among the most expensive basic operations you can do on integers, so aside from the fact that this method is constant time, that time is likely going to be pretty small.

To solve your original question:

def max_decent(digits):
    a, b = partition35(digits)
    if a < 0:
        print(-1)
    else:
        print(''.join(('5'*a, '3'*b)))

Answer 2

I got it down to \$O(n)\$; complexity. I'm not fluent in Python, so this solution is in JavaScript, but it's reads fairly easily (especially if you're familiar with C-like syntax)

function decent(digits) {
    var result = "";
    // First, let's get as few 3s as possible for the least significant digits
    while (digits % 3 !== 0) {
        result += "33333";
        digits -= 5;
        // We've reached a point where digits is still not divisible by 3
        // But we're out of digits, so... Not possible.
        if (digits < 0) {
            return "-1";
        }
    }
    // Here, digits is definitely divisible by 3, so just repeat the 5s
    return "5".repeat(digits) + result;
}