Introduction to problem statement
In this blog, we will discuss a number theory problem asked frequently in Interviews.
The problem is to find the number formed by K times alternatively reducing X and adding Y to 0.
We are asked to update 0 by decrementing X and incrementing Y a total of K times.
Sample Examples
Example 1
Sample Input:
3
2
5
Sample Output:
1
Explanation
Say K=3, X=2, Y=5.
Therefore operations to be performed are:
Operation 1: 0-2=-2.
Operation 2: -2+5=3.
Operation 3: 3-2=1.
So, the answer returned will be 1.
Since K given is 3, so we performed 3 operations.
Example 2
Sample Input:
4
1
100
Sample Output:
198
Explanation
Say K=4, X=1, Y=100.
Therefore operations to be performed are:
Operation 1: 0-1=-1.
Operation 2: -1+100=99.
Operation 3: 99-1=98.
Operation 4: 98-100=198.
So, the answer returned will be 198.
Since K given is 4, so we performed 4 operationsAlso see, Euclid GCD Algorithm
Brute-force Approach
The naive approach to find the number formed by K times, alternatively reducing X and adding Y to 0 is given below. We need to execute the operation k times in order as given in the problem and then find the required answer.
Let a loop run k times.
⬇
For all even rounds, subtract x and for all odd rounds, subtract y.
⬇
Output the answer calculated from the above two steps.
PseudoCode
___________________________________________________________________
procedure positionAfterKJumps(int X, int Y, int K):
___________________________________________________________________
1. for(i=0 to i=K):
if(i%2 == 0): ans=ans-X
Else: ans=ans+Y
2. return ans
end procedureImplementation in C++
// C++ program to find number formed by K times, alternatively reducing X and adding Y to 0
#include <bits/stdc++.h>
using namespace std;
int positionAfterKJumps(int X, int Y, int K)
{
int ans = 0;
for(int i = 0; i < K; i++) {
if(i%2==0) {
ans -= X;
} else {
ans += Y;
}
}
return ans;
}
int main()
{
int X, Y, K;
cin>>X>>Y>>K;
cout << positionAfterKJumps(X, Y, K);
return 0;
}
Input
2
5
3Output
1
Complexity Analysis
Time Complexity: O(k).
Analysing Time Complexity: Since the loop is traversed k times.
Space complexity: O(1), as no extra space has been used besides variables to compute the answer.
38+ registered 