TheJobOverflow | TCS | Online Assessments

Question: TCS | Online Assessments | Deleting Channel

Entering edit mode

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.

ADD COMMENT • link

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. enter image description here

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 &lt;bits/stdc++.h&gt; //this header includes all other headers
using namespace std;
int solve(int n, int k) {// n -&gt; nos of channels; k -&gt; nos of channels to skip
    vector&lt;bool&gt; channel(n, true); //ith element is false if ith channel is deleted
    int i = 0, cnt = n; // i -&gt; current channel; cnt -&gt; nos of undeleted channels
    while (cnt &gt; 1) {
        for (int j = 0; j &lt; 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 &gt;&gt; n &gt;&gt; k; 
    cout &lt;&lt; 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 &gt; 1 ? (solve(n-1, k) + k - 1) % n + 1 : 1;
}

This is all the code!

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

ADD COMMENT • link 2.6 years ago admin 1.6k

Entering edit mode

can you explain the solution2.?

ADD REPLY • link 2.0 years ago

Vikas Kumar Vikrant • 0

Entering edit mode

To simplify the problem, we can consider the index of the last remaining node instead of its value. Let's denote the index of the last remaining node as f(n,k). Then, we can derive the following recursive formula:

f(1,k) = 1 (base case: there is only one node left) f(n,k) = (f(n-1,k) + k) % n (general case: remove the kth node, and start from the next node in a circular manner)

The base case is straightforward: if there is only one node left, then its index is 1.

For the general case, we first remove the kth node from the list, which leaves us with a circular linked list containing (n-1) nodes. Then, we start from the next node in a circular manner (i.e., the node immediately to the right of the removed node). This is equivalent to shifting the indices of the remaining nodes by k positions to the left. For example, if we remove the kth node from a list of n nodes, then the index of the next node becomes (k+1)%n. To obtain the index of the last remaining node in the original list of n nodes, we need to shift the index back by k positions to the right. This is achieved by taking the modulo of (f(n-1,k) + k) with n.

Therefore, we can use this recursive formula to compute the index of the last remaining node for any given n and k. For example, if n=7 and k=3, we can compute f(7,3) as follows:

f(1,3) = 1 (base case)

f(2,3) = (f(1,3) + 3) % 2 = 0

f(3,3) = (f(2,3) + 3) % 3 = 1

f(4,3) = (f(3,3) + 3) % 4 = 1

f(5,3) = (f(4,3) + 3) % 5 = 4

f(6,3) = (f(5,3) + 3) % 6 = 2

f(7,3) = (f(6,3) + 3) % 7 = 3

Therefore, the last remaining node in a cycle of 7 nodes, with every 3rd node removed, is the node with index 3.

ADD REPLY • link 2.0 years ago