Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
The set [1, 2, 3, ..., n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
"123""132""213""231""312""321"Given n and k, return the kth permutation sequence.
Example 1:
Input: n = 3, k = 3 Output: "213"
Example 2:
Input: n = 4, k = 9 Output: "2314"
Example 3:
Input: n = 3, k = 1 Output: "123"
Constraints:
1 <= n <= 91 <= k <= n!Problem summary: The set [1, 2, 3, ..., n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence for n = 3: "123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation sequence.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math
3 3
4 9
3 1
next-permutation)permutations)import java.util.*;
class Solution {
public String getPermutation(int n, int k) {
List<Integer> numbers = new ArrayList<>();
for (int i = 1; i <= n; i++) numbers.add(i);
int[] fact = new int[n + 1];
fact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
// Convert k to 0-indexed rank.
k--;
StringBuilder ans = new StringBuilder();
// Pick one digit per position using factorial blocks.
for (int i = n; i >= 1; i--) {
int blockSize = fact[i - 1];
int idx = k / blockSize;
k %= blockSize;
ans.append(numbers.remove(idx));
}
return ans.toString();
}
}
import (
"strconv"
"strings"
)
func getPermutation(n int, k int) string {
numbers := make([]int, n)
for i := 0; i < n; i++ {
numbers[i] = i + 1
}
fact := make([]int, n+1)
fact[0] = 1
for i := 1; i <= n; i++ {
fact[i] = fact[i-1] * i
}
k-- // 0-indexed rank
var b strings.Builder
for i := n; i >= 1; i-- {
blockSize := fact[i-1]
idx := k / blockSize
k %= blockSize
b.WriteString(strconv.Itoa(numbers[idx]))
numbers = append(numbers[:idx], numbers[idx+1:]...)
}
return b.String()
}
class Solution:
def getPermutation(self, n: int, k: int) -> str:
numbers = list(range(1, n + 1))
fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i - 1] * i
k -= 1 # 0-indexed rank
ans = []
for i in range(n, 0, -1):
block_size = fact[i - 1]
idx = k // block_size
k %= block_size
ans.append(str(numbers.pop(idx)))
return ''.join(ans)
impl Solution {
pub fn get_permutation(n: i32, k: i32) -> String {
let n = n as usize;
let mut numbers: Vec<i32> = (1..=n as i32).collect();
let mut fact = vec![1; n + 1];
for i in 1..=n {
fact[i] = fact[i - 1] * i as i32;
}
let mut k = k - 1; // 0-indexed rank
let mut ans = String::new();
for i in (1..=n).rev() {
let block_size = fact[i - 1];
let idx = (k / block_size) as usize;
k %= block_size;
let val = numbers.remove(idx);
ans.push_str(&val.to_string());
}
ans
}
}
function getPermutation(n: number, k: number): string {
const numbers: number[] = [];
for (let i = 1; i <= n; i++) numbers.push(i);
const fact: number[] = Array(n + 1).fill(1);
for (let i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
k--; // 0-indexed rank
let ans = '';
for (let i = n; i >= 1; i--) {
const blockSize = fact[i - 1];
const idx = Math.floor(k / blockSize);
k %= blockSize;
ans += String(numbers[idx]);
numbers.splice(idx, 1);
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Simulate the process step by step — multiply n times, check each number up to n, or iterate through all possibilities. Each step is O(1), but doing it n times gives O(n). No extra space needed since we just track running state.
Math problems often have a closed-form or O(log n) solution hidden behind an O(n) simulation. Modular arithmetic, fast exponentiation (repeated squaring), GCD (Euclidean algorithm), and number theory properties can dramatically reduce complexity.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.