Can somebody help me with this problem?

Statement: - What is the maximum possible n digit number starting from 0 we can make in K steps using only 2 operations:- multiplying by 3 or incrementing by 2.

EXAMPLE : N =2 K = 5; -> (0->2->6->8->24->72) 72 IS THE ANSWER

N = 2 , K = 51 -> (0->2->6->8->10->30->32->96->98). 98 is the maximum we can get so need to check for rest of the moves.

My 2 state-recursive solution:-

public static void largestNDigitNumber(long[] highest, long maxValue, long k, long currentValue) {
    if (highest[0] == (maxValue - 2)) return; //no need to do anything as we get 98 as highest.
    if (k < 0) return; //checking for steps

    if (highest[0] < currentValue && currentValue <= (maxValue - 2)) {
        highest[0] = currentValue;
    }

    largestNDigitNumber(highest, maxValue, (k - 1), (currentValue * 3));
    largestNDigitNumber(highest, maxValue, (k - 1), (currentValue   2));
}


public static void main(String[] args) {
    int n = 2;
    long k = 51;
    long maxValue = (long) Math.pow(10, n);
    long[] highest = new long[1];
    largestNDigitNumber(highest, maxValue, (k - 1), 2);
    if (highest[0] < (long) Math.pow(10, (n - 1))) {
        System.out.println("-1"); // if it is not possible to make n digit in given steps
    } else System.out.println(highest[0]);
}

when "k" is small it is giving the correct answer but for bigger values of "k", it does not show any input. for n=2 and k = 51, it does not show anything.

please help me to improve this code

CodePudding user response：

The question is equivalent to asking what is the largest base 3 number that is less than 10^n/2, and has digit sum plus length less than or equal to k 1. (The answer is then double the base 3 number).

For example, N=2 K=5. What's the largest base 3 number that's less than 50, with length plus digit sum less than or equal to 6. Answer: 1100 (36 decimal), so the answer to the original question is 36*2=72.

For N=2, K=51, the largest base-3 number that's less than 50 is 2001 (49 decimal) and has length sum plus digit sum = 7, which is way less than K 1.

Given this representation, it's easy to solve the problem in O(n) time (in fact, you can solve it using pencil and paper). The length d of the base-3 number is as large as possible such that 3^d < 10^n/2 and d<=K. Then fill in the digits of the number greedily from the most-significant first until you have digit sum K 1-d (or you run out of digits).

Equivalence

First note that without loss of generality you can assume you never have three 2 operations in a row, since that can be done more efficiently by inserting a single 2 operation to before the most recent *3 (or simply replacing it by 2 * 3 if there's no *3 operation). Suppose you have represented the current number as a doubled base-3 number. A 2 operation corresponds to adding 1 to the bottom digit (this never overflows into the next column thanks to the observation above). A *3 operation moves all the digits up one column, introducing a 0 as the bottom digit. Note that because the number is doubled, the 2 operation adds just 1 to the base-3 number!

From this, you can see that you can count the number of operations from observation of the doubled base-3 number. Because *3 introduces a new digit, and 2 increases the digit sum by 1, so the number of operations is equal to the number of digits plus 1, plus the digit sum.

As an example. Suppose you have the doubled base-3 number 2 * 2101, then this is equivalent to 2 * (1 3*3*(1 3*(1 1)))) = (2 3*3*(2 3*(2 2))).

CodePudding user response：

I tried something like this. it seems to work fine.

getMaxNumber(2, 5)  ==> 72
getMaxNumber(2, 51) ==> 98


private int getMaxNumber(int n, int k){
    int N = 0;
    for (int i = 0; i < n; i  ) {
        N = N * 10   9;
    }
    int[] result = new int[1];
    helper(N, k, 0, 0, result);
    return result[0];
}


private void helper(int N, int K, int n, int k, int[] result){
    if(n > N) return;
    if(k <= K){
        result[0] = Math.max(result[0], n);
    }
    if(n > 0)
        helper(N, K, n * 3, k   1, result);
    helper(N, K, n   2, k   1, result);
}

CodePudding user response：

Keeping with the style of your original recursive method. I modified it a bit to produce a working solution:

public static long largestNDigitNumber(int n, long currentK, long maxK, long currentValue) {
    if (currentK > maxK || n < 1 || maxK < 1) return 0;
    if (currentValue >= Math.pow(10, n))
        return 0;
    
    long c1 = largestNDigitNumber(n, currentK   1, maxK, currentValue * 3);
    long c2 = largestNDigitNumber(n, currentK   1, maxK, currentValue   2);

    if (c1 == 0 && c2 == 0)
        return currentValue;
    return c1 > c2 ? c1 : c2;
}


public static void main(String[] args) {
    int n = 2;
    long k = 51;
    long largest = largestNDigitNumber(n, 0, k, 0);
    System.out.println(largest); //98
}

This recursive method returns values here instead of using an array. Hence the check if one returned value is bigger than the other or they are both 0 before returning.