Find next smallest number that's representable as a sum of distinct powers of 3

Question

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

Answer 1

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