Entering edit mode

Click here to Practice

Submit Problem to OJ

**Delete TV Channel**

There are *n* channels on your TV. The channels are arranged in such a manner that after the nth channel, it again starts with the first one, and channels are numbered from *1 to n*. More formally, on moving from the *ith* channel brings you to the *(i+1)th* channel for *1<=i< n*, and moving clockwise from the *nth* channel brings you to the *1st* channel.

**The rules of switching TV channels are as follows:**

Start from the 1st channel.

Count the next k channels clockwise, including the channel you started at. The counting wraps around the circle and may count some channels more than once.

The last channel you counted gets deleted from the TV.

If there is still more than one channel in the circle, go back to step 2, starting from the channel immediately clockwise of the channel which was just deleted and repeat.

Else, watch the last channel on the TV and enjoy the day.

Given the number of TV Channels *n*, and an integer *k*. Return the channel number you are watching when only one channel is left.

Find the channel you are watching.

**Note:**

*Clockwise*direction can be defined as the movement from left to right and again from the starting element after the*nth*element.*1<=k<= n <= 500*

**Input Format**

- The first line contains a positive integer
*n*. - The second line contains a positive integer
*k*.

**Output Format**

Print a single Integer x denoting the channel number you are watching at the end(when only 1 channel is left).

**Sample Testcase #0**

```
Testcase Input
5
2
Testcase Output
3
```

**Explanation**

**Here are the steps of the game:**

- Start at channel 1.
- Count 2 channels clockwise, which are channel 1 and 2.
- Channel 2 gets deleted. The next start is channel 3.
- Count 2 channels clockwise, which are channel 3 and 4.
- Channel 4 gets deleted. The next start is channel 5.
Count 2 channels clockwise, which are channel 5 and 1.

**- Channel 5 gets deleted. Only channel 3 is left, So, we will watch channel 3.**

Entering edit mode

This problem can be solved even for higher constraints. Since N <= 500, O(N * N) solution using recursion will also fetch 100/100.

Here is a diagram representing illustrating the sample input.

The basic idea of this solution is to simply simulate the whole process. The simplest solution we can implement would require only an array. The following pseudocode illustrates the same.

```
#include <bits/stdc++.h> //this header includes all other headers
using namespace std;
int solve(int n, int k) {// n -> nos of channels; k -> nos of channels to skip
vector<bool> channel(n, true); //ith element is false if ith channel is deleted
int i = 0, cnt = n; // i -> current channel; cnt -> nos of undeleted channels
while (cnt > 1) {
for (int j = 0; j < k; ++j, ++i)
while(!channel[i % n]) ++i;
channel[(i - 1) % n] = false;
--cnt;
}
for (i = 0; !channel[i]; ++i);
return i + 1;
}
int main() {
int n, k;
cin >> n >> k;
cout << solve(n, k);
return 0;
}
```

- Time Complexity :
**O(N * K)** - Space Complexity :
**O(N)** - Note : Same idea can be implemented using
**Linked List**instead of arrays to get a faster solution.

However, there exists a more efficient, simpler to code solution to this problem which will also work for constraints like N <= 10^8. **Note** : This version of constraint has been asked as it is in several product based companies coding round.

```
int solve(int n, int k) {
return n > 1 ? (solve(n-1, k) + k - 1) % n + 1 : 1;
}
```

This is all the code!

- Time Complexity :
**O(N)** - Space Complexity :
**O(1)**

Loading Similar Posts