Problem 196063 · hard · Phase 01 Prerequisites & Setup

The Magician's Perfect Riffle

loops · simulation · invariants

A magician holds a deck of n cards, numbered 0 to n - 1 from top to bottom. One perfect riffle works like this:

  1. Cut the deck into a top pile of the first (n + 1) // 2 cards and a bottom pile of the rest.
  2. Interleave them, starting with the top pile: top card of the top pile, top card of the bottom pile, second card of the top pile, second card of the bottom pile, and so on. When n is odd the top pile has one extra card, which ends up at the very bottom.

Write riffles_to_restore(n) that returns the smallest positive number of perfect riffles after which every card is back in its starting position.

Examples

Input:  n = 6
Output: 4
Explanation: 012345 -> 031425 -> 043215 -> 024135 -> 012345

Input:  n = 5
Output: 4

Input:  n = 52
Output: 8

Constraints

  • 1 <= n <= 10**6

Goals

  • Turn a list-shuffling rule into a formula for one card's new position
  • Follow a single element instead of rebuilding the whole list
  • Argue why one card is enough to know when every card is home
Starting Python…