Two functions with different definition.

 funcA:
    a = a - 2;
    b = b - 1;

 funcB: 
    a = a - 1;
    b = b - 2;

Our aim to get the number of operations when both a = 0 and b = 0;

Sample input: a = 4, b = 2

  call funcA:
     a become 2, b become 1;
  again call funcA
     a become 0, b become 0;

total no of operation performed 2 0 = 2 so returned 2;

Sample input 2: a = 3, b = 3

  call funcA:
     a become 1, b become 2;
  call funcB
     a become 0, b become 0;

total no of operation performed 1 1 = 2 so returned 2;

CodePudding user response：

Let's start from special cases:

• if a < 0 or b < 0 we have no solution
• if a = 0 and b <> 0 or a <> 0 and b = 0 we have no solution
• if a > 2 * b or b > 2 * a we have no solution

If we use funcA x times and funcB y times and get 0 from both a and b we can write

a - 2 * x - y = 0
b - 2 * y - x = 0

Let's solve this system of linear equations for x and y:

2 * x   y = a
2 * y   x = b

The solution is

x = (2 * a - b) / 3
y = (2 * b - a) / 3

So if we have an integer solution for x and y we should perform funcA x times, funcB y times

Code (Java):

public static int Solve(int a, int b) {
  // beware integer overflow! we use long in case a = 2_000_000_000 provided 
  long x = (2L * a - b) / 3;
  long y = (2L * b - a) / 3;

  return ((x >= 0 && y >= 0 && (2L * b - a) % 3 == 0 && (2L * a - b) % 3 == 0))
    ? (int)(x   y)
    : -1; // impossible
}

As one can see, we have a direct solution with O(1) time and space complexity; there's no need in dynamic programming