Adjust Dumbbells

The idea is to make the mathematical equation of the given problem and iterate over all the possible values. Let’s say we take x weights of A kgs each and y weights of B kgs each, such that the weight that Ninja wants is K kgs.

The equation becomes

A*x + B*y = K.

This is similar to the equation of a line in the 2D plane. But in the 2D plane, the number of points is infinite. So, we will find the range of values of x and y.

The minimum value of x and y is 0, as we can use only one weight to make the desired weight. The maximum value of x will be when y is 0 and vice versa. So, when x = 0, y = K/B and when y = 0, x = K/A.

So, we will iterate over all the possible values of x and y and count the number of points (i, j) in which the equation holds true.

The steps are as follows:

• Initialize an integer answer to 0 that stores the final answer.
• Iterate from x = 0 to K/A:
  • Iterate from y = 0 to K/B:
    • If the point (i, j) satisfies the given equation, i.e., x*A + y*B = K, then er will increment the answer by 1.
• We will return answer as the final answer.

From the above approach, we deduced that the equation in consideration is

A*x + B*y = K.

Here, we will iterate for y only and then find x from the given equation,

x = (K - B*y)/A.

Here is a condition, this equation only holds true if K - B*y is non-negative and is divisible by A. 

So, we will iterate from y = 0 to K/B and check for the above condition.

To optimize the above-discussed solution, we can use the minimum of A and B in place of A.

The steps are as follows:

• Initialize an integer answer to 0 that stores the final answer.
• If A is greater than B, then swape the values of A and B.
• Iterate from y = 0 to K/B:
  • If K - y*B is divisible by A, then we will increment answer by 1.
• We will return answer as the final answer.

We found the values in the previous approach by iterating, but if we carefully observe

From the equation,

x = (K - B*y)/A.

if y1 is the smallest value that satisfies the equation, what will be the value that satisfies the equation?

Isn’t it y1 + A?

Further terms satisfying the given equations are y1 + 2*A, y1 + 3*A, …… y1 + p*A.

It is an arithmetic progression with the number of terms = p + 1.

y1 + p*A <= K/B

So, numberOfTerms = (K/B - y1)/A………(a)

In order to decrease the number of computations, we will divide A, B, and K by the greatest common divisor of A and B at the beginning.

The steps are as follows:

• Base Condition 1: If K is zero, then there will exist only one pair (0, 0). So, return 1 as the final answer.
• We will find the greatest common divisor of A and B and store it in a variable gcdOfBoth.
• Base Condition 2: If K is not divisible by gcdOfBoth, return 0 as the final answer.
• Divide A, B, and K by gcdOfBoth.
• Initialize an integer y1 to 0 that stores the first value that satisfies the given equation.
• If A is greater than B, then swap the values of A and B.
• Iterate from y1 = 0 to K/B:
  • If K - y1*B is divisible by A, break the loop.
• Initialize an integer numberOfTerms which is equal to the value of p in the formula (a).
• Initialize an integer answer which stores the final answer and is equal to numberOfTerms + 1.
• We will return answer as the final answer.

Continuing from the previous approach, the idea is to use the Extended Euclid Algorithm to find the first value of x divisible by B.

From the equation,

x = (K - B*y)/A

We have to find smallest value of y(let’s say y1) such that,

(K - B*y1)%A = 0

K%A - (B%A)(y1%A) = 0

As y1 will always be lesser than A,

we get

y1 = (K - A*x)/B….from the above equation

Taking modulo both the sides, 

y1%A = (K/B)%A - (A*x/B)%A = (K/B)%A…….Equation (b)

The above term (A*x/B)%A will be equal to 0 as the inside term is a multiple of A.

So, the equation becomes,

y1%A = (K/B)%A

So, we will calculate (K/B)%A. Now, we have the value of y1%A, but we need the value of y1, not y1%A. So, we have to find the modular inverse of y1%A with respect to A. Here, Extended Euclid Algorithm will be used.

Here is an excellent link to learn how to find the modulo inverse using the Euclid algorithm.

The overview is:

We will calculate the gcd of A and B-> Divide A, B, and K by the gcd of A and B -> then get the value of y1 from equation (b) -> Find the number of terms(p) -> number of Terms + 1 is the final answer.

The steps are as follows:

• Base Condition 1: If K is zero, then there will exist only one pair (0, 0). So, return 1 as the final answer.
• We will find the greatest common divisor of A and B and store it in a variable gcdOfBoth.
• Base Condition 2: If K is not divisible by gcdOfBoth, return 0 as the final answer.
• Divide A, B, and K by gcdOfBoth.
• Find the first value of y1 using the extended Euclid algorithm.
• Find the number of terms(numberOfTerms) using the formula numberOfTerms = (K/B - y1)/A.
• Return numberOfTerms+1 as the final answer.