Given a positive integer A, return an array of minimum length whose elements are powers of 3 and have the sum of all the elements equal to A.

For input A = 13:

3⁰ = 1, 3¹ = 3, 3² = 9.
1 3 9 = 13.

So A = 13 can be represented as the sum of 1, 3 and 9.

Is there a better way to solve this problem?

public static int[] getSolve(int A) {

    List<Integer> binary = new ArrayList<>();
    while (A > 0) {
        int r = A % 3;
        binary.add(r);
        A /= 3;
    }

  //  System.out.println(binary.toString());
    List<Integer> res = new ArrayList<>();
    int j = 0;
    for (int i = 0; i < binary.size(); i  ) {
        if (binary.get(i) != 0) {
            while (j < binary.get(i)) {
                res.add((int) Math.pow(3, i));
                j  ;
            }
            j =0;
        }
    }
    return res.stream().mapToInt(i -> i).toArray();
}

CodePudding user response：

The answer to this question is always the base 3 representation, which is also known as ternary.

My biggest suggestion is that there is no need for your binary data structure. As you are finding the remainders, right there and then you can see whether the remainder is and add the appropriate powers of 3 to your answer.

CodePudding user response：

For python folks, it can be useful

class Solution: # @param A : integer # @return a list of integers def solve(self, A): bits = [] solution = []

    while(A != 0):
        bits.append(A % 3);
        A = A // 3;
    
    for i in range(len(bits)):
        if(bits[i] != 0):
            tmp = 0;
            while(tmp < bits[i]):
                solution.append(pow(3, i));
                tmp = tmp   1
    return solution