Java programming question, issue with logic

Question

Recently I came across a programming question like, given a total and an input k find the total number of ways we can reach total with numbers from 1 to k.

for eg: total = 5, k = 3

the output should be 5

cause we can reach 5 in 5 ways using 1, 2 and 3 as below

1+1+1+1+1

1+1+1+2

1+2+2

1+1 +3

2 + 3

I have come up with the below logic, but it's not completely working as am not doing backtracking (I suppose) which I am not sure on how to do

private static int totalways(int total, int k) {
        List<Integer> arr =  new ArrayList();
        for (int i=0; i<total; i++) {
            arr.add(1);
        }
        int count = 1;
        boolean breakLoop = true;
        while (breakLoop) {
            int last = arr.size()-1;
            for (int i=last; i>=1; i--) {
                if (arr.get(i) + arr.get(i-1) <= k) {
                    count++;
                    int sum = arr.get(i) + arr.get(i-1);
                    arr.remove(i-1);
                    arr.remove(i-1);
                    arr.add(sum);
                }
            }
            if (arr.size() == 2){
                breakLoop = false;
            }
        }
        return count;
    }

Any help is appreciated.

figure out all the ways to get to 1 with all the numbers from 1 to 1 then figure out all the ways to get to 2 with all the numbers from 1 to 2 then .... until you get to k You can use the results of the lower numbers to solve those of the higher. This technique is called Dynamic Programming. — AminM
– AminM, Commented Jul 30, 2020 at 10:28

Stef · Accepted Answer · 2020-07-31 10:24:14Z

2

This is a classic problem that can easily be solved with dynamic programming. See also this similar problem: https://en.wikipedia.org/wiki/Change-making_problem

The first observation is that when you're trying to write total with numbers up to k, you can either use k, or not use k.

If you use k, then you still have to make total - k with numbers up to k. If you don't use k, then you're effectively making total with numbers up to k-1.

If we call c[total][k] the number of ways to make total with numbers up to k, then our observation gives us a formula: c[total][k] = c[total-k][k] + c[total][k-1].

EDIT: This formula is true iff k <= total. If k > total, then c[total][k] = c[total][k-1].

We can also observe that c[0][k] = 1 for all values of k, and c[total][0] = 0 for any total > 0.

Writing a naive recursive program to use our recursive formula would be horrible; we'd end up with an exponential complexity because for every call we need to make two recursive calls.

Instead, we can use our formula in a dynamic programming algorithm, simply filling a two-dimensional array c[][] with the results:

int[][] c = new int[total+1][k+1];
for (int n = 1; n <= total; ++n)
{
  c[n][0] = 0;
}
for (int j = 0; j <= k; ++j)
{
  c[0][j] = 1;
}
for (int n = 1; n <= total; ++n)
{
  int maxj = (k <= n) ? k : n;         // maxj = min(k,n)
  for (int j = 1; j <= maxj; ++j)      // case j <= n
  {
    c[n][j] = c[n-j][j] + c[n][j-1];
  }
  for (int j = maxj + 1; j <= k; ++j)  // case j > n
  {
    c[n][j] = c[n][j-1];
  }
}
return c[total][k];

EDIT: taking into account the case k > total, as per comments

edited Jul 31, 2020 at 10:24

answered Jul 30, 2020 at 15:10

Stef

15.7k2 gold badges22 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Stef Over a year ago

Can you elaborate on why you think it's not working? At least for total=5 and k=3 it outputs 5, the same result as you got by hand.

robin Over a year ago

I am getting an error saying Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 6 at com.expediagroup.api.Test.getWays(Test.java:23) at com.expediagroup.api.Test.main(Test.java:6) to fix it I added a check before doing c[n][j] = c[n-j][j] + c[n][j-1]; by verifying n is always greater than j, then it's returning 0.

Stef Over a year ago

Oops, my mistake. Fixed.

cquezel · Accepted Answer · 2020-08-02 15:12:02Z

1

Taking your example, total = 5, k = 3, the problem is to find a function "f(k, total)" that will try all values "v" from 1 to k to sum to a total that is "total" minus "v".

f(3, 5) then does:
"f" tries 1 and must now sum to 4 i.e. calls f(3, 4)
"f" tries 2 and must now sum to 3 i.e. calls f(3, 3)
"f" tries 3 and must now sum to 2 i.e. calls f(3, 2)

Notice that function f calls itself. This is called a recursive call. Recursive calls are generally simple solutions when you need backtracking.

This will generate a call tree like:

f(3, 5) {}
    f(3, 4) {1}
        f(3, 3) {1, 1}
            f(3, 2) {1, 1, 1}
                f(3, 1) {1, 1, 1, 1}
                    f(3, 0) {1, 1, 1, 1, 1} *
                f(3, 0) {1, 1, 1, 2} *
            f(3, 1) {1, 1, 2}
                f(3, 0) {1, 1, 2, 1} *
            f(3, 0) {1, 1, 3}
...

The calling process stops when the "total" parameter is 0.

This solution generates identical combinations {1,1,1,2}, {1,1,2,1}... To fix this, you could modify the f logic so that you could never try a value "v" higher than what your parent caller tried. Your function logic would be:

f(k, total) {
    ...
    for v in 1 to min(k, total) {
        ...
        f(v, total - v)
    }
}

The new complete call tree would be:

f(3, 5) {}
    f(1, 4) {1}
        f(1, 3) {1, 1}
            f(1, 2) {1, 1, 1}
                f(1, 1) {1, 1, 1, 1}
                    f(1, 0) {1, 1, 1, 1, 1} *
    f(2, 3) {2}
        f(1, 2) {2, 1}
            f(1, 1) {2, 1, 1}
                f(1, 0) {2, 1, 1, 1} *
        f(2, 1) {2, 2}
            f(1, 0) {2, 2, 1} *
    f(3, 2) {3}
        f(1, 1) {3, 1}
            f(1, 0) {3, 1, 1} *
        f(2, 0) {3, 2} *

All you have to do now is accumulate the found solutions when total gets to 0.

To do this you will need some type of stack to which you will add the current solution.

void f(int k, int total) {
    if (total == 0) {
        System.err.println("add a copy of the current stack to your solutions.");
        return;
    }
    for (int v = 1; v <= Math.min(k, total); ++v) {
        f(v, total - v);
    }
}

edited Aug 2, 2020 at 15:12

answered Jul 30, 2020 at 12:33

cquezel

4,5451 gold badge34 silver badges36 bronze badges

3 Comments

robin Over a year ago

why we are using v in 1 to minimum(k, total), we know always k is the smallest one. tried the solution it's printing till 2 2 1 and then failing.

robin Over a year ago

still the same exception, can you write it any programming language and test it.

cquezel Over a year ago

@robin in my solution k will not always be smaller than total. Look at the call tree f(2, 1), f(3,2)

Collectives™ on Stack Overflow

Java programming question, issue with logic

2 Answers 2

3 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related