N people from 1 to N are standing in the queue at a movie ticket counter. It is a weird counter, as it distributes tickets to the first K people and then the last K people and again the first K people, and so on, once a person gets a ticket moves out of the queue. The task is to find the last person to get the ticket.
Examples:
Input: N = 9, K = 3
Output: 6
Explanation: Starting queue will like {1, 2, 3, 4, 5, 6, 7, 8, 9}. After the first distribution queue will look like {4, 5, 6, 7, 8, 9}. And after the second distribution queue will look like {4, 5, 6}. The last person to get the ticket will be 6.Input: N = 5, K = 1
Output: 3
Explanation: Queue starts as {1, 2, 3, 4, 5} -> {2, 3, 4, 5} -> {2, 3, 4} -> {3, 4} -> {3}, Last person to get a ticket will be 3.
Solving problem Using Deque:
The given approach utilizes a deque (double-ended queue) data structure to simulate the ticket distribution process. The main idea is to pop elements from both ends of the queue in a specific pattern until only one person remains.
Follow the steps to solve the problem:
- Iterate from i = 1 to N and add each person’s number to the back of the deque using dq.push_back(i).
- Perform the following steps until the size of the deque becomes 1:
- Initialize a variable i to 0 to keep track of the number of elements popped from the deque.
- Pop K elements from the front of the deque by repeatedly calling dq.pop_front() while i < K and the deque’s size is not 1.
- Reset i to 0.
- Pop K elements from the back of the deque by repeatedly calling dq.pop_back() while i < K and the deque’s size is not 1.
- Return the element at the front of the deque using dq.front(), which represents the last person to receive a ticket.
Below is the Implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int distributeTicket(int N, int K){ // Step 1: Create deque deque<int> dq; // Step 2: Initialize the deque with // person numbers for (int i = 1; i <= N; i++) { dq.push_back(i); } // Step 3: Perform ticket // distribution process while (dq.size() != 1) { int i = 0; // Pop K elements from the // front of the deque while (dq.size() != 1 && i < K) { dq.pop_front(); i++; } i = 0; // Pop K elements from the back // of the deque while (dq.size() != 1 && i < K) { dq.pop_back(); i++; } } // Step 4: Return the last person // to receive a ticket return dq.front();}// Drivers codeint main(){ int N = 9; int K = 3; // Function call int lastPerson = distributeTicket(N, K); cout << lastPerson << endl; return 0;} |
Java
import java.util.ArrayDeque;import java.util.Deque;class Solution { public static int distributeTicket(int N, int K) { // Step 1: Create deque Deque<Integer> dq = new ArrayDeque<>(); // Step 2: Initialize the deque // with person numbers for (int i = 1; i <= N; i++) { dq.addLast(i); } // Step 3: Perform ticket // distribution process while (dq.size() != 1) { int i = 0; // Pop K elements from the // front of the deque while (dq.size() != 1 && i < K) { dq.removeFirst(); i++; } i = 0; // Pop K elements from the // back of the deque while (dq.size() != 1 && i < K) { dq.removeLast(); i++; } } // Step 4: Return the last person // to receive a ticket return dq.getFirst(); } public static void main(String[] args) { int N = 9; int K = 3; // Function call int lastPerson = distributeTicket(N, K); System.out.println(lastPerson); }}// This code is contributed by Jeetu Bangari |
Python3
from collections import dequedef distributeTicket(N, K): # Step 1: Create deque dq = deque() # Step 2: Initialize the deque # with person numbers for i in range(1, N + 1): dq.append(i) # Step 3: Perform ticket # distribution process while len(dq) != 1: i = 0 # Pop K elements from the front # of the deque while len(dq) != 1 and i < K: dq.popleft() i += 1 i = 0 # Pop K elements from the back # of the deque while len(dq) != 1 and i < K: dq.pop() i += 1 # Step 4: Return the last person # to receive a ticket return dq[0]N = 9K = 3# Function calllastPerson = distributeTicket(N, K)print(lastPerson)# This code is contributed by Jeetu Bangari |
C#
using System;using System.Collections.Generic;using System.Linq;class Program{ static void Main(string[] args) { int N = 9; int K = 3; // Function call int lastPerson = distributeTicket(N, K); Console.WriteLine(lastPerson); } public static int distributeTicket(int N, int K) { // Step 1: Create deque LinkedList<int> dq = new LinkedList<int>(); // Step 2: Initialize the deque // with person numbers for (int i = 1; i <= N; i++) { dq.AddLast(i); } // Step 3: Perform ticket // distribution process while (dq.Count() != 1) { int i = 0; // Pop K elements from the // front of the deque while (dq.Count() != 1 && i < K) { dq.RemoveFirst(); i++; } i = 0; // Pop K elements from the // back of the deque while (dq.Count() != 1 && i < K) { dq.RemoveLast(); i++; } } // Step 4: Return the last person // to receive a ticket return dq.First.Value; }}// This code is contributed by Sakshi |
Javascript
function distributeTicket(N, K) { // Step 1: Create deque const dq = []; // Step 2: Initialize the deque //with person numbers for (let i = 1; i <= N; i++) { dq.push(i); } // Step 3: Perform ticket //distribution process while (dq.length !== 1) { let i = 0; // Pop K elements from the front //of the deque while (dq.length !== 1 && i < K) { dq.shift(); i++; } i = 0; // Pop K elements from the //back of the deque while (dq.length !== 1 && i < K) { dq.pop(); i++; } } // Step 4: Return the last person //to receive a ticket return dq[0];}const N = 9;const K = 3;//Function callconst lastPerson = distributeTicket(N, K);console.log(lastPerson);// This code is contributed by Jeetu Bangari |
Output
6
Time complexity: O(N), where N is the number of people in the queue.
Auxiliary space: O(N), since the deque stores N elements in the worst case.
Two-Pointer Approach
The given approach utilizes a two-pointer approach to find the last person to receive a ticket. It maintains two pointers, left and right, which represent the leftmost and rightmost positions in the queue, respectively.
Follow the steps to solve the problem:
- Initialize left to 1 (representing the leftmost position in the queue) and right to n (representing the rightmost position in the queue).
- Initialize firstDistribution to true, indicating the first distribution of tickets.
- While the left is less than or equal to right, repeat the following steps:
- If firstDistribution is true (indicating the first distribution):
- If left + k is less than right, update left to left + k (moving k positions forward).
- Otherwise, return right as the last person to receive a ticket.
- If firstDistribution is false (indicating the last distribution):
- If right – k is greater than left, update right to right – k (moving k positions backward).
- Otherwise, return left as the last person to receive a ticket.
- Toggle the value of firstDistribution (alternate between the first and last distribution).
- If firstDistribution is true (indicating the first distribution):
- If the while loop condition is not satisfied, return 0 as an error value.
Below is the Implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int distributeTicket(int N, int K){ int left = 1; int right = N; bool firstDistribution = true; while (left <= right) { if (firstDistribution) { if (left + K < right) left += K; else return right; } else { if (right - K > left) right -= K; else return left; } firstDistribution = !firstDistribution; } // Error value return 0;}// Drivers codeint main(){ int N = 9; int K = 3; // Function call int lastPerson = distributeTicket(N, K); cout << lastPerson << endl; return 0;} |
Java
public class Solution { public static int distributeTicket(int N, int K) { int left = 1; int right = N; boolean firstDistribution = true; while (left <= right) { if (firstDistribution) { if (left + K < right) left += K; else return right; } else { if (right - K > left) right -= K; else return left; } firstDistribution = !firstDistribution; } // Error Value return 0; } public static void main(String[] args) { int N = 9; int K = 3; // Function call int lastPerson = distributeTicket(N, K); System.out.println(lastPerson); }}// This code is contributed by Jeetu Bangari |
Python3
def distributeTicket(N, K): left = 1 right = N firstDistribution = True while left <= right: if firstDistribution: if left + K < right: left += K else: return right else: if right - K > left: right -= K else: return left firstDistribution = not firstDistribution# Error value return 0 N = 9K = 3# Function calllastPerson = distributeTicket(N, K)print(lastPerson)# This code is contributed by Jeetu Bangari |
C#
using System;public class GFG{ public static int DistributeTicket(int N, int K) { int left = 1; int right = N; bool firstDistribution = true; while (left <= right) { if (firstDistribution) { if (left + K < right) left += K; else return right; } else { if (right - K > left) right -= K; else return left; } firstDistribution = !firstDistribution; } // Error value return 0; } public static void Main(string[] args) { int N = 9; int K = 3; // Function call int lastPerson = DistributeTicket(N, K); Console.WriteLine(lastPerson); }} |
Javascript
function distributeTicket(N, K) { let left = 1; let right = N; let firstDistribution = true; while (left <= right) { if (firstDistribution) { if (left + K < right) left += K; else return right; } else { if (right - K > left) right -= K; else return left; } firstDistribution = !firstDistribution; } // Error value return 0; }const N = 9;const K = 3;// Function callconst lastPerson = distributeTicket(N, K);console.log(lastPerson);// This code is contributed by Jeetu Bangari |
Output
6
Time complexity: O(N), where N is the number of people in the queue.
Auxiliary space: O(1), as it uses constant space.
Calculation-based Approach
The given approach uses a calculation-based approach to determine the last person to receive a ticket. It avoids explicitly simulating the distribution process and directly computes the result based on the values of N and K.
Follow the steps to solve the problem:
- Perform the following checks in order to determine the last person to receive a ticket:
- If m is even and r is non-zero, return K * (m/2) + r. This means that there are an even number of complete distributions, and there are some remaining people after that.
- If m is odd and r is zero, return K * (m/2 + 1). This means that there are an odd number of complete distributions and no remaining people.
- If m is odd and r is non-zero, return K * (m/2 + 1) + 1. This means that there are an odd number of complete distributions, and there are some remaining people after that.
- If m is even and r is zero, return K * (m/2) + 1. This means that there are an even number of complete distributions and no remaining people.
- If none of the above conditions are satisfied, return an appropriate error value.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int distributeTicket(int N, int K){ int m = N / K; int r = N % K; if (m % 2 == 0 && r) return K * (m / 2) + r; if (m % 2 && !r) return K * (m / 2 + 1); if (m % 2 && r) return K * (m / 2 + 1) + 1; if (m % 2 == 0 && !r) return K * (m / 2) + 1; // Error value return 0;}// Drivers codeint main(){ int N = 9; int K = 3; // Function call int lastPerson = distributeTicket(N, K); cout << lastPerson << endl; return 0;} |
Java
public class Solution { public static int distributeTicket(int N, int K) { int m = N / K; int r = N % K; if (m % 2 == 0 && r != 0) return K * (m / 2) + r; if (m % 2 != 0 && r == 0) return K * (m / 2 + 1); if (m % 2 != 0 && r != 0) return K * (m / 2 + 1) + 1; if (m % 2 == 0 && r == 0) return K * (m / 2) + 1; // Error value return 0; } public static void main(String[] args) { int N = 9; int K = 3; // Function call int lastPerson = distributeTicket(N, K); System.out.println(lastPerson); }}// This code is contributed by Jeetu Bangari |
Python3
def distributeTicket(N, K): m = N // K r = N % K if m % 2 == 0 and r: return K * (m // 2) + r if m % 2 and not r: return K * (m // 2 + 1) if m % 2 and r: return K * (m // 2 + 1) + 1 if m % 2 == 0 and not r: return K * (m // 2) + 1 # Error value return 0N = 9K = 3# Function calllastPerson = distributeTicket(N, K)print(lastPerson)# This code is contributed by Jeetu Bangari |
C#
using System;public class GFG{ public static int DistributeTicket(int N, int K) { int m = N / K; int r = N % K; if (m % 2 == 0 && r != 0) return K * (m / 2) + r; if (m % 2 != 0 && r == 0) return K * (m / 2 + 1); if (m % 2 != 0 && r != 0) return K * (m / 2 + 1) + 1; if (m % 2 == 0 && r == 0) return K * (m / 2) + 1; // Error value return 0; } public static void Main() { int N = 9; int K = 3; // Function call int lastPerson = DistributeTicket(N, K); Console.WriteLine(lastPerson); }} |
Javascript
function distributeTicket(N, K) { let m = Math.floor(N / K); let r = N % K; if (m % 2 === 0 && r !== 0) return K * Math.floor(m / 2) + r; if (m % 2 !== 0 && r === 0) return K * Math.floor(m / 2) + K; if (m % 2 !== 0 && r !== 0) return K * Math.floor(m / 2) + K + 1; if (m % 2 === 0 && r === 0) return K * Math.floor(m / 2) + 1; // Error value return 0; }const N = 9;const K = 3;//Function Callconst lastPerson = distributeTicket(N, K);console.log(lastPerson);// This code is contributed by Jeetu Bangari |
Output
6
Time complexity: O(1), because the calculations and checks performed are constant time operations.
Auxiliary space: O(1), as there is constant space used.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
