## Introduction to problem statement

In this blog, we will discuss a number theory problem asked frequently in Interviews.

The problem is to **f****ind 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.