4
\$\begingroup\$

I'm solving this challenge:

Given a positive integer number, you have to find the smallest good number greater than or equal to the given number. The positive integer is called good if it can be represented as a sum of distinct powers of 3 (i.e. no duplicates of powers of 3 are allowed).

The code passes all the test cases in the editor, but when submitted to online judge it is failing because of time limit exceeded. Give time limit 1 second, my code execution is taking 1.01 second


t = int(input())
while t > 0:
    N = int(input())
    i=N
    while i > 0:
        if i % 3 == 2:
            N=N+1
            i=N
            continue
        i //= 3
    print(N)
    t = t - 1

Test Case

Input:

5
3
46
65
89
113

Output:

3
81
81
90
117
\$\endgroup\$
1
  • \$\begingroup\$ Your test case output is missing the output from $5$. It should be $9$, I believe. \$\endgroup\$ Jul 5, 2021 at 3:54

1 Answer 1

8
\$\begingroup\$

The best approach would be to use ternary numbers, at least at development. Number that's representable as a sum of power of 3 in ternary would consist of 0's and 1's only. So:

repeat:

  • convert the number to ternary;
  • if there's no 2's in it - return it;
  • if there're 2's - find the leftmost 2, change all digits starting with it into 0 and add 1 to the next digit to the left.

I think it can be done in one pass of conversion into ternary.

Update: here's my code, it's \$O(log(n))\$ (yours is \$O(nlog(n))\$):

def find_distinct_pow3(number):
    result = 0 
    power = 1
    while number:
        number, digit = divmod(number, 3)
        if digit<2:
            result += power*digit #just copying the digit into the result
        else:
            result = 0 #discarding current result (after the digit 2)
            number += 1 #increasing the digit before 2
        power *= 3
    return result
\$\endgroup\$
1
  • \$\begingroup\$ execution time 0.02 sec,thanks \$\endgroup\$ Jul 4, 2021 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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