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