Reach the Target Number using only the other two numbers
I have two numbers L and R, L means left and R means Right. I need to get to a certain number (F) using L and R. Every time I have to start from zero as starting.
Example: L: 1 R: 2 F: 3
SO the minimum number of steps required to go to F is 3. Ans: First R, Second R, Third L.
In this case, I need to find the minimum number of ways to do this.
My approach:
Quo = F/R;
Remain : F%R;
x*R-Y*L = Remain
==> (x*R - Remain)/L = Y
this equation is break when (x*R - Remain)%L = 0, so we find x and y from the equation above.
So final Steps would be Quo + x(No. of right steps) + y( no. of left steps).
For Above Example :
Quo = 3/2 = 1;
Remain = 3%2 =1;
Y = (x*2 -1)/1
(x*2 -1)%1 is zero for x=1;
Now increase x from zero,
So x is 1, y is 1
Final Ans = Quo (1) + x (1) + y(1) = 3.
My code:
#include <iostream>
using namespace std;
int main()
{
int F,R,L;
cin >> F;
cin >> R;
cin >> L;
int remain = F%R;
int quo = F/R;
int Right = 0;
int left = 0;
int mode = 1;
while( mode !=0)
{
Right++;
mode = (R*Right - remain)%L;
left = (R*Right - remain)/L;
}
int final = quo + Right + left;
cout << final;
}
But I don't think this is a good approach as I put x in a loop which can be quite costly
Could you please suggest me a good approach to address this issue?
source to share
In the equation below
x*R - Remain = 0modL
where R, L and Remain are fixed.
It can be written as
((x*R)mod L - Remain mod L) mod L = 0
If Remain mod L = 0, then x * R must be a multiple of L, which makes x equal to 0modL. The x values can be 0, nR, where n is an integer.
So, you can try x between 0 and L-1 to find x.
So your loop can run from 0 to L-1, which will keep the end loop going.
Please note that this mod is different from%. -1 mod L = L-1
whereas-1%L = -1
There is another approach.
x*R mod L - Remain mod L = 0 mod L
leads to
x*R mod L = Remain mod L
(x* (R mod L)) mod L = (Remain mod L)
You can compute the inverse R (say Rinv
) in the L field (if it exists) and compute x = (Remain*Rinv)modL
. If the inversion does not exist, it means that the equation cannot be fulfilled.
Note. I am not a mathematical expert. So please give your opinion if something is wrong.
See: https://www.cs.cmu.edu/~adamchik/21-127/lectures/congruences_print.pdf
source to share