Adjust Dumbbells

The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow. The first line contains three space-separated integers, ‘A’, ‘B’, and ‘K’, denoting the first weight that he bought, the second weight that he bought, and the weight he wants to lift, respectively.

You are not required to print the expected output, it has already been taken care of. Just implement the function. Two ways are considered different if the number of times a is used or the number of times b is used is different in the two ways.

1<= T <= 10^4 1 <= A, B <= 10^9 0 <= K <= 10^9 Where ’T’ is the number of test cases, 'A' is the first weight that Ninja bought, ‘B’ is the second weight that Ninja bought, and ‘K’ is the weight Ninja wants to lift respectively. Time Limit: 1 sec

In the first test case, the weights that Ninja bought are 2 and 3 kgs. The weight that he wants to lift is 5 kgs. There is only one way to make the combination of 5 kgs using both weights by choosing one weight of each type. So, the answer is 1. In the second test case, the weights that Ninja bought are 2 and 3 kgs. The weight that he wants to lift is 12 kgs. There are three ways to make the combination of 12 kgs. The first way is to take 6 weights of 2 kgs each, the second way is to take 4 weights of 3 kgs, and the last way is to take two weights of 3 kgs each and three weights of 2 kgs each. So, the answer is 3.

Brute Force

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.

Time Complexity

O((K^2)/(A*B)), where A is the first weight Ninja bought, B is the second weight Ninja bought, and K is the weight Ninja wants to lift.

As we are iterating over the possible values of x from 0 to K/A and then iterating over the possible values of y from 0 to K/B. So, the overall time complexity is O((K^2)/A*B).

Space Complexity

O(1).

As we are using constant extra space. So, the overall space complexity is O(1).

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation for Sample Input 1 :

Sample Input 2 :

Sample Output 2 :