1 day ago

John 500

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:

1. Start from the 1st channel.

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

3. The last channel you counted gets deleted from the TV.

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

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

7 hours ago

admin 1.2k

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.

Solution 1

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.

Solution 2 (Optimal)

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)