Friday, January 10, 2025
Google search engine
HomeData Modelling & AIFind out the person who got the ticket last.

Find out the person who got the ticket last.

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 code
int 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 deque
 
 
def 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 = 9
K = 3
 
# Function call
lastPerson = 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 call
const 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 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 code
int 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 = 9
K = 3
# Function call
lastPerson = 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 call
const 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 code
int 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 0
 
 
N = 9
K = 3
 
# Function call
lastPerson = 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 Call
const 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!

Commit to GfG’s Three-90 Challenge! Purchase a course, complete 90% in 90 days, and save 90% cost click here to explore.

Last Updated :
04 Sep, 2023
Like Article
Save Article


Previous

<!–

8 Min Read | Java

–>


Next


<!–

8 Min Read | Java

–>

Share your thoughts in the comments

RELATED ARTICLES

Most Popular

Recent Comments