CODEWITHSUNDEEP
pythonalgorithmpython-3.xbig-otime-complexity
benSooraj
benSooraj

Reputation: 465

Decent Numbers | Help Reduce Time Complexity

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 2 '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.

Upvotes: 0

Views: 1307

Answers (1)

Pham Trung
Pham Trung

Reputation: 11284

To solve this problem, we need to make few observations:

  • the largest "decent number" having 'N' digits is the number that contains the most number of digit 5. It will have the form 5555...3333...

  • As Number of times 5 appears is divisible by 3, so we have three cases:

    • If N is divided by 3, so there is no digit 3 .

    • If N % 3 = 1, so we need to add a times digit 3 to the result, and a % 3 == 1 to make the total number of digit 5 (N - a) divisible by 3 , so a % 3 == 1 and a % 5 == 0 -> a = 10. (Notice that a has to be smallest among all valid values). Final result will have (N - 10) digits of 5 and 10 digits of 3.

    • Similarly, if N % 3 = 2, so we need to add a times digit 3 to the result, a % 3 == 2 and a % 5 == 0 -> a = 5;

With those observations, you can solve this problem in O(1) for each N.

Upvotes: 5

Related Questions