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
orb < 0
we have no solution - if
a = 0
andb <> 0
ora <> 0
andb = 0
we have no solution - if
a > 2 * b
orb > 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