1.
Introduction to problem statement
1.1.
Sample Examples
2.
Brute-force Approach
2.1.
PseudoCode
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimised Approach
3.1.
PseudoCode
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Find the number formed by K times, alternatively reducing X and adding Y to 0

Urwashi Priya
0 upvote

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 operations``````

Also 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 procedure``````

Implementation 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
3``````

Output

``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.

Optimised Approach

The optimised approach to find the number formed by K times, alternatively reducing X and adding Y to 0 is given below. We have to first find overall numbers to be added and subtracted separately, then find the required answer. And we use the concept that subtraction is nothing but negative of addition. If K given to us is an odd number, then the decrementation operation has to be performed once more as we are starting our operation by decrementation only.

Find the total number to be incremented.

It would be Y*K/2.

Find the total number to be decremented.

It would be -1*(K/2+K%2).

Since decrementation operation is to be performed, therefore multiplying by -1.

If K given is an odd number, then the decrementation operation has to be performed once more, so we added K%2.

Output the sum of above two steps.

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try try here

PseudoCode

``````___________________________________________________________________
procedure positionAfterKJumps(int X, int Y, int K):
___________________________________________________________________
1.  addY = Y * (K / 2)
2.  reduceX = -1 * X * (K / 2 + K % 2)
end procedure
___________________________________________________________________``````

Implementation 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)
{
// result obtained after incrementation operation
int addY = Y * (K / 2);

// result obtained after decrementation operation
int reduceX = -1 * X * (K / 2 + K % 2);

}

int main()
{
int X, Y, K;
cin>>X>>Y>>K;
cout << positionAfterKJumps(X, Y, K);

return 0;
}``````

Input

``````2
5
3``````

Output

``1``

Complexity Analysis

Time Complexity: O(1).

Analysing Time Complexity: All operations take constant time.

Space complexity: O(1), as no extra space has been used.

FAQs

1. What is a modulo operator?
This operator returns the remainder. Sometimes, it is used to check the divisibility.

2. What is another way to find if an integer is even or odd without using the modulo operator?
There are two ways to do this: method 1 is to use the bitwise(&) operator. Method 2 involves multiplying and dividing the number by 2. Again divide the result by 2 and multiply the new result by 2. If the number equals our input number, then it is an even number otherwise not.

3. What is meant by constant time complexity?
It means that regardless of the number of inputs, the same time is taken.

Key Takeaways

This article taught us how to find the number formed by K times, alternatively reducing X and adding Y to 0 by approaching the problem using number theory concept. We discussed our problem's implementation using illustrations, pseudocode, and proper code.

We hope you could take away all critical and conceptual techniques like analysing problems by walking over the execution of the given examples and finding out the pattern followed.
Now, we recommend you to practice problem sets based on number theory to master your fundamentals and enhance your learning. You can get a wide range and variety of questions similar to this on Coding Ninjas Studio

It's not the end. Must solve the problem of similar types.
Happy Coding.

Live masterclass