Funcia
Lv.1queuesimulation

Last Card Standing

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

n cards numbered 1 to n are stacked with card 1 on top and card n at the bottom. Until one card remains, repeat:

  1. Discard the top card.
  2. Move the card that is now on top to the bottom.

Return the number of the last remaining card.

Examples

nresult
44
64
11

Example 1 — 1 2 3 4 → 3 4 2 → 2 4 → 4.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(n: int) → int

Constraints

  • 1≤1 \le n ≤1,000,000\le 1{,}000{,}000

Expected complexity

Time
O(N)
Space
O(N)

Examples

nExpected
44
64
11

Hint

Hint

Removing from the front and appending to the back is exactly what a queue does in O(1)O(1), so the whole process is O(N)O(N). Erasing the first element of an array (erase(begin), pop(0), remove(0)) shifts every other element and makes the process O(N2)O(N^2), which exceeds the time limit. (List the answers for small n and you may spot a closed form.)

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.