Permutation Sequence (Kth)

🎯

Permutation Sequence (Kth)

hardBACKTRACKINGAmazonGoogleFacebook

Imagine you have a list of tasks to perform in every possible order, but you want to quickly jump to the k-th order without enumerating all permutations.

💡 This problem asks for the k-th permutation sequence of numbers from 1 to n. Beginners often struggle because generating all permutations is expensive and unnecessary. Understanding how to directly compute the k-th permutation using factorial math is key.

📋

Problem Statement

Given n and k, return the k-th permutation sequence of the numbers [1, 2, ..., n] in lexicographical order. Input: two integers n and k. Output: a string representing the k-th permutation.

1 ≤ n ≤ 91 ≤ k ≤ n!

💡

Example

Input"n = 3, k = 3"

Output"213"

The permutations of [1,2,3] in order are: 123, 132, 213, 231, 312, 321. The 3rd is '213'.

• n = 1, k = 1 → output '1' (smallest input)
• k = 1 → output is the first permutation in ascending order
• k = n! → output is the last permutation in descending order
• n = 9, k = 362880 (9!) → largest input within constraints

⚠️

Common Mistakes

Forgetting to convert k to zero-based index

Incorrect index calculation leads to wrong permutation

✅ Always do k = k - 1 before calculations

Not removing used numbers from the list

Repeated numbers appear in the result

✅ Remove the selected number from the available list after choosing

Using factorial values incorrectly or not precomputing

Wrong index calculation or inefficient repeated factorial computation

✅ Precompute factorials once before main loop

Trying to generate all permutations for large n

Solution times out or crashes due to memory/time limits

✅ Use direct computation approach instead of brute force

Not handling edge cases like k=1 or k=n!

Incorrect output or runtime errors

✅ Test and handle boundary cases explicitly if needed

🧠

Brute Force (Generate All Permutations)

💡 This approach exists to build intuition by enumerating all permutations and picking the k-th. It is straightforward but inefficient, illustrating why direct computation is needed.

Intuition

Generate all permutations of [1..n] in lex order using backtracking, then return the k-th one.

Algorithm

1. Initialize a list to store all permutations.
2. Use backtracking to generate all permutations of [1..n].
3. Stop when the k-th permutation is generated.
4. Return the k-th permutation as a string.

💡 The challenge is understanding how backtracking generates permutations and why this approach is too slow for large n.

</>

Code

def getPermutation(n, k):
    res = []
    used = [False] * n
    path = []
    def backtrack():
        if len(path) == n:
            res.append(''.join(map(str, path)))
            return
        for i in range(n):
            if not used[i]:
                used[i] = True
                path.append(i + 1)
                backtrack()
                path.pop()
                used[i] = False
    backtrack()
    return res[k - 1]

# Driver code
if __name__ == '__main__':
    print(getPermutation(3, 3))  # Output: '213'

Line Notes

res = []Stores all permutations generated so far

used = [False] * nTracks which numbers are already in the current permutation path

def backtrack():Defines the recursive function to build permutations

if len(path) == n:Base case: a full permutation is formed

res.append(''.join(map(str, path)))Add the current permutation as a string to results

for i in range(n):Try each number from 1 to n if not used

used[i] = TrueMark number as used before recursion

path.append(i + 1)Add number to current permutation path

backtrack()Recurse to build deeper permutations

path.pop()Backtrack by removing last number

used[i] = FalseMark number as unused for other branches

return res[k - 1]Return the k-th permutation from the list

import java.util.*;
public class Solution {
    List<String> res = new ArrayList<>();
    boolean[] used;
    int n;
    public String getPermutation(int n, int k) {
        this.n = n;
        used = new boolean[n];
        backtrack(new StringBuilder());
        return res.get(k - 1);
    }
    private void backtrack(StringBuilder path) {
        if (path.length() == n) {
            res.add(path.toString());
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                path.append(i + 1);
                backtrack(path);
                path.deleteCharAt(path.length() - 1);
                used[i] = false;
            }
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.getPermutation(3, 3)); // Output: 213
    }
}

Line Notes

List<String> res = new ArrayList<>()Stores all permutations generated

boolean[] usedTracks which numbers are used in current path

backtrack(new StringBuilder())Starts recursion with empty path

if (path.length() == n)Base case: full permutation formed

res.add(path.toString())Add current permutation to results

for (int i = 0; i < n; i++)Try each number from 1 to n

used[i] = trueMark number as used before recursion

path.append(i + 1)Add number to current path

backtrack(path)Recurse deeper

path.deleteCharAt(path.length() - 1)Backtrack by removing last number

used[i] = falseMark number as unused for other branches

return res.get(k - 1)Return the k-th permutation

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<string> res;
    vector<bool> used;
    int n;
    void backtrack(string &path) {
        if ((int)path.size() == n) {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                path.push_back('1' + i);
                backtrack(path);
                path.pop_back();
                used[i] = false;
            }
        }
    }
    string getPermutation(int n, int k) {
        this->n = n;
        used.assign(n, false);
        string path = "";
        backtrack(path);
        return res[k - 1];
    }
};

int main() {
    Solution sol;
    cout << sol.getPermutation(3, 3) << endl; // Output: 213
    return 0;
}

Line Notes

vector<string> resStores all generated permutations

vector<bool> usedTracks usage of numbers in current permutation

void backtrack(string &path)Recursive function to build permutations

if ((int)path.size() == n)Base case: full permutation formed

res.push_back(path)Add current permutation to results

for (int i = 0; i < n; i++)Try each number from 1 to n

used[i] = trueMark number as used before recursion

path.push_back('1' + i)Add number to current path

backtrack(path)Recurse deeper

path.pop_back()Backtrack by removing last number

used[i] = falseMark number as unused for other branches

return res[k - 1]Return the k-th permutation

function getPermutation(n, k) {
    const res = [];
    const used = new Array(n).fill(false);
    const path = [];
    function backtrack() {
        if (path.length === n) {
            res.push(path.join(''));
            return;
        }
        for (let i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                path.push(i + 1);
                backtrack();
                path.pop();
                used[i] = false;
            }
        }
    }
    backtrack();
    return res[k - 1];
}

// Test
console.log(getPermutation(3, 3)); // Output: 213

Line Notes

const res = []Stores all permutations generated

const used = new Array(n).fill(false)Tracks which numbers are used in current path

function backtrack()Recursive function to build permutations

if (path.length === n)Base case: full permutation formed

res.push(path.join(''))Add current permutation as string to results

for (let i = 0; i < n; i++)Try each number from 1 to n

used[i] = trueMark number as used before recursion

path.push(i + 1)Add number to current path

backtrack()Recurse deeper

path.pop()Backtrack by removing last number

used[i] = falseMark number as unused for other branches

return res[k - 1]Return the k-th permutation

⏱

Complexity

TimeO(n! * n)

SpaceO(n! * n)

Generating all permutations takes n! time and each permutation is length n, so total O(n! * n).

💡 For n=9, n! is 362,880, which is huge and impractical to generate fully.

Interview Verdict: TLE

This approach times out for larger n because it generates all permutations instead of directly computing the k-th.

🧠

Backtracking with Early Stop

💡 This approach improves brute force by stopping recursion once the k-th permutation is found, saving some time but still not efficient enough for large n.

Intuition

Generate permutations in lex order, but stop recursion as soon as the k-th permutation is reached.

Algorithm

1. Initialize a global counter to track how many permutations have been generated.
2. Use backtracking to generate permutations in lex order.
3. When the counter reaches k, record the current permutation and stop recursion.
4. Return the recorded permutation.

💡 The key difficulty is managing the global count and stopping recursion early to save time.

</>

Code

def getPermutation(n, k):
    used = [False] * n
    path = []
    count = [0]
    result = ['']
    def backtrack():
        if len(path) == n:
            count[0] += 1
            if count[0] == k:
                result[0] = ''.join(map(str, path))
            return
        if result[0]:
            return
        for i in range(n):
            if not used[i]:
                used[i] = True
                path.append(i + 1)
                backtrack()
                path.pop()
                used[i] = False
    backtrack()
    return result[0]

# Driver code
if __name__ == '__main__':
    print(getPermutation(3, 3))  # Output: '213'

Line Notes

count = [0]Tracks how many permutations have been generated so far

result = ['']Stores the k-th permutation once found

if len(path) == n:Base case: full permutation formed

count[0] += 1Increment count when a permutation is completed

if count[0] == k:Check if current permutation is the k-th

result[0] = ''.join(map(str, path))Save the k-th permutation

if result[0]:Stop recursion early if k-th permutation found

for i in range(n):Try each number from 1 to n

used[i] = TrueMark number as used

path.append(i + 1)Add number to current path

backtrack()Recurse deeper

path.pop()Backtrack by removing last number

used[i] = FalseMark number as unused

import java.util.*;
public class Solution {
    List<String> res = new ArrayList<>();
    boolean[] used;
    int n, count = 0;
    String result = "";
    public String getPermutation(int n, int k) {
        this.n = n;
        used = new boolean[n];
        backtrack(new StringBuilder(), k);
        return result;
    }
    private void backtrack(StringBuilder path, int k) {
        if (path.length() == n) {
            count++;
            if (count == k) {
                result = path.toString();
            }
            return;
        }
        if (!result.isEmpty()) return;
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                path.append(i + 1);
                backtrack(path, k);
                path.deleteCharAt(path.length() - 1);
                used[i] = false;
            }
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.getPermutation(3, 3)); // Output: 213
    }
}

Line Notes

int count = 0Tracks how many permutations generated

String result = ""Stores the k-th permutation once found

if (path.length() == n)Base case: full permutation formed

count++Increment count when a permutation is completed

if (count == k)Check if current permutation is the k-th

result = path.toString()Save the k-th permutation

if (!result.isEmpty()) returnStop recursion early if k-th permutation found

for (int i = 0; i < n; i++)Try each number from 1 to n

used[i] = trueMark number as used

path.append(i + 1)Add number to current path

backtrack(path, k)Recurse deeper

path.deleteCharAt(path.length() - 1)Backtrack by removing last number

used[i] = falseMark number as unused

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<bool> used;
    int n, count = 0;
    string result = "";
    void backtrack(string &path, int k) {
        if ((int)path.size() == n) {
            count++;
            if (count == k) {
                result = path;
            }
            return;
        }
        if (!result.empty()) return;
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                path.push_back('1' + i);
                backtrack(path, k);
                path.pop_back();
                used[i] = false;
            }
        }
    }
    string getPermutation(int n, int k) {
        this->n = n;
        used.assign(n, false);
        string path = "";
        backtrack(path, k);
        return result;
    }
};

int main() {
    Solution sol;
    cout << sol.getPermutation(3, 3) << endl; // Output: 213
    return 0;
}

Line Notes

int count = 0Tracks how many permutations generated

string result = ""Stores the k-th permutation once found

if ((int)path.size() == n)Base case: full permutation formed

count++Increment count when a permutation is completed

if (count == k)Check if current permutation is the k-th

result = pathSave the k-th permutation

if (!result.empty()) returnStop recursion early if k-th permutation found

for (int i = 0; i < n; i++)Try each number from 1 to n

used[i] = trueMark number as used

path.push_back('1' + i)Add number to current path

backtrack(path, k)Recurse deeper

path.pop_back()Backtrack by removing last number

used[i] = falseMark number as unused

function getPermutation(n, k) {
    const used = new Array(n).fill(false);
    const path = [];
    let count = 0;
    let result = '';
    function backtrack() {
        if (path.length === n) {
            count++;
            if (count === k) {
                result = path.join('');
            }
            return;
        }
        if (result) return;
        for (let i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                path.push(i + 1);
                backtrack();
                path.pop();
                used[i] = false;
            }
        }
    }
    backtrack();
    return result;
}

// Test
console.log(getPermutation(3, 3)); // Output: 213

Line Notes

let count = 0Tracks how many permutations generated

let result = ''Stores the k-th permutation once found

if (path.length === n)Base case: full permutation formed

count++Increment count when a permutation is completed

if (count === k)Check if current permutation is the k-th

result = path.join('')Save the k-th permutation

if (result) returnStop recursion early if k-th permutation found

for (let i = 0; i < n; i++)Try each number from 1 to n

used[i] = trueMark number as used

path.push(i + 1)Add number to current path

backtrack()Recurse deeper

path.pop()Backtrack by removing last number

used[i] = falseMark number as unused

⏱

Complexity

TimeO(k * n)

SpaceO(n)

In worst case, we generate up to k permutations, each of length n, so O(k * n).

💡 If k is large (close to n!), this is still very slow and impractical.

Interview Verdict: TLE for large k

Early stopping helps but still too slow for large inputs; motivates direct computation.

🧠

Optimal Direct Computation Using Factorial Number System

💡 This approach uses math to directly compute the k-th permutation without generating all permutations, making it efficient and scalable.

Intuition

Each position in the permutation can be determined by dividing k by factorials of remaining digits, selecting the appropriate number from the unused list.

Algorithm

1. Precompute factorials from 0! to (n-1)!.
2. Create a list of numbers from 1 to n.
3. Adjust k to zero-based index (k = k - 1).
4. For each position, determine the index by dividing k by factorial of remaining positions.
5. Append the number at that index to the result and remove it from the list.
6. Update k to k modulo factorial of remaining positions.
7. Return the concatenated result string.

💡 The key insight is mapping k to indices using factorial blocks, which avoids generating permutations.

</>

Code

def getPermutation(n, k):
    factorial = [1] * n
    for i in range(1, n):
        factorial[i] = factorial[i - 1] * i
    numbers = list(range(1, n + 1))
    k -= 1  # zero-based index
    result = []
    for i in range(n - 1, -1, -1):
        idx = k // factorial[i]
        k %= factorial[i]
        result.append(str(numbers[idx]))
        numbers.pop(idx)
    return ''.join(result)

# Driver code
if __name__ == '__main__':
    print(getPermutation(3, 3))  # Output: '213'

Line Notes

factorial = [1] * nInitialize factorial array to store factorials up to (n-1)!

for i in range(1, n)Compute factorial values iteratively

numbers = list(range(1, n + 1))List of available numbers to pick from

k -= 1Convert k to zero-based index for calculation

for i in range(n - 1, -1, -1)Iterate from highest factorial to lowest

idx = k // factorial[i]Determine index of number to pick based on k

k %= factorial[i]Update k to remainder for next iteration

result.append(str(numbers[idx]))Add selected number to result

numbers.pop(idx)Remove used number from list

import java.util.*;
public class Solution {
    public String getPermutation(int n, int k) {
        int[] factorial = new int[n];
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
        List<Integer> numbers = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            numbers.add(i);
        }
        k--;
        StringBuilder result = new StringBuilder();
        for (int i = n - 1; i >= 0; i--) {
            int idx = k / factorial[i];
            k %= factorial[i];
            result.append(numbers.get(idx));
            numbers.remove(idx);
        }
        return result.toString();
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.getPermutation(3, 3)); // Output: 213
    }
}

Line Notes

int[] factorial = new int[n]Array to store factorials up to (n-1)!

for (int i = 1; i < n; i++)Compute factorial values iteratively

List<Integer> numbers = new ArrayList<>()List of available numbers to pick from

k--Convert k to zero-based index

for (int i = n - 1; i >= 0; i--)Iterate from highest factorial to lowest

int idx = k / factorial[i]Determine index of number to pick

k %= factorial[i]Update k for next iteration

result.append(numbers.get(idx))Add selected number to result

numbers.remove(idx)Remove used number from list

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> factorial(n, 1);
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
        vector<int> numbers;
        for (int i = 1; i <= n; i++) {
            numbers.push_back(i);
        }
        k--;
        string result;
        for (int i = n - 1; i >= 0; i--) {
            int idx = k / factorial[i];
            k %= factorial[i];
            result += to_string(numbers[idx]);
            numbers.erase(numbers.begin() + idx);
        }
        return result;
    }
};

int main() {
    Solution sol;
    cout << sol.getPermutation(3, 3) << endl; // Output: 213
    return 0;
}

Line Notes

vector<int> factorial(n, 1)Stores factorials up to (n-1)!

for (int i = 1; i < n; i++)Compute factorial values iteratively

vector<int> numbersList of available numbers to pick from

k--Convert k to zero-based index

for (int i = n - 1; i >= 0; i--)Iterate from highest factorial to lowest

int idx = k / factorial[i]Determine index of number to pick

k %= factorial[i]Update k for next iteration

result += to_string(numbers[idx])Add selected number to result

numbers.erase(numbers.begin() + idx)Remove used number from list

function getPermutation(n, k) {
    const factorial = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        factorial[i] = factorial[i - 1] * i;
    }
    const numbers = [];
    for (let i = 1; i <= n; i++) {
        numbers.push(i);
    }
    k--;
    let result = '';
    for (let i = n - 1; i >= 0; i--) {
        const idx = Math.floor(k / factorial[i]);
        k %= factorial[i];
        result += numbers[idx];
        numbers.splice(idx, 1);
    }
    return result;
}

// Test
console.log(getPermutation(3, 3)); // Output: 213

Line Notes

const factorial = new Array(n).fill(1)Array to store factorials up to (n-1)!

for (let i = 1; i < n; i++)Compute factorial values iteratively

const numbers = []List of available numbers to pick from

k--Convert k to zero-based index

for (let i = n - 1; i >= 0; i--)Iterate from highest factorial to lowest

const idx = Math.floor(k / factorial[i])Determine index of number to pick

k %= factorial[i]Update k for next iteration

result += numbers[idx]Add selected number to result

numbers.splice(idx, 1)Remove used number from list

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Computing factorials is O(n), and removing elements from the list is O(n) per removal, total O(n^2).

💡 For n=9, this is very efficient compared to brute force, running in milliseconds.

Interview Verdict: Accepted

This is the optimal approach for this problem and is expected in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code the optimal direct computation approach after briefly mentioning brute force.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n! * n)	O(n! * n)	Yes (deep recursion)	Yes	Mention only - never code
2. Backtracking with Early Stop	O(k * n)	O(n)	Yes	Yes	Mention as improvement, but not optimal
3. Optimal Direct Computation	O(n^2)	O(n)	No	N/A	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and learn how to explain your thought process clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach to show understanding.Step 3: Discuss its inefficiency and propose early stopping.Step 4: Introduce the factorial number system for direct computation.Step 5: Code the optimal solution and test with examples.

Time Allocation

Clarify: 2min → Approach discussion: 5min → Code: 10min → Testing & optimization: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of permutations, ability to optimize brute force, and knowledge of factorial math for direct computation.

Common Follow-ups

• What if numbers are not 1 to n but an arbitrary list? → Sort and apply same logic.
• How to handle duplicates in the input? → Use backtracking with pruning or count permutations carefully.

💡 These follow-ups test your ability to generalize and handle variations of the problem.

🔍

Pattern Recognition

When to Use

1) Asked for k-th permutation or sequence; 2) Input size too large for brute force; 3) Lexicographical order mentioned; 4) Factorials or counting permutations involved.

Signature Phrases

k-th permutationlexicographical ordersequence number

NOT This Pattern When

Generating all permutations without order or combinations problems

Similar Problems

Next Permutation - find next lexicographical permutationPermutation II - handle duplicates in permutations

Practice

1. You are given an array of integers and need to find the lexicographically next greater permutation of its elements. Which approach guarantees finding this next permutation in optimal time without generating all permutations?

easy

A. Scan from the end to find a pivot where the sequence stops increasing, swap with the smallest greater element on the right, then reverse the suffix.

B. Apply a greedy approach by swapping the first two elements that are out of order from the start.

C. Use dynamic programming to store all permutations and find the next one by memoization.

D. Generate all permutations, sort them, and pick the next one after the current permutation.

Solution

1. Step 1: Understand the problem requirement

   The problem asks for the lexicographically next greater permutation, which requires finding the next sequence just larger than the current one.

2. Step 2: Identify the optimal approach

   The approach scanning from the end to find a pivot where the sequence stops increasing, swapping with the smallest greater element on the right, then reversing the suffix guarantees the next permutation in O(n) time without generating all permutations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Brute force is correct but inefficient; DP and greedy do not guarantee correct next permutation [OK]

Hint: Next permutation uses pivot-swap-reverse pattern [OK]

Common Mistakes:

• Thinking brute force is optimal
• Using greedy from start fails on suffix order

2. What is the time complexity of the backtracking with bitmask optimization approach for counting beautiful arrangements of size n?

medium

A. O(n * n!)

B. O(n^2)

C. O(n * 2^n)

D. O(n!)

Solution

1. Step 1: Identify the search space

   The algorithm explores permutations of n numbers, which is n! in worst case.

2. Step 2: Consider pruning and bitmask usage

   Bitmask helps track used numbers efficiently, pruning invalid branches but the total number of recursive calls is proportional to n * n! because for each position, up to n choices are tried.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores permutations with n choices per position, leading to O(n * n!) complexity [OK]

Hint: Backtracking permutations with bitmask -> O(n * n!) time [OK]

Common Mistakes:

• Confusing bitmask with exponential 2^n complexity
• Assuming polynomial due to pruning

3. What is the time complexity of the optimal in-place next permutation algorithm for an input array of length n?

medium

A. O(n) because it scans the array a constant number of times

B. O(n log n) because it sorts the suffix after the pivot

C. O(n!) due to generating all permutations

D. O(n^2) because it swaps elements multiple times in nested loops

Solution

1. Step 1: Identify the main operations

   The algorithm scans from the end to find the pivot (O(n)), then scans again to find the swap element (O(n)), and finally reverses the suffix (O(n)).

2. Step 2: Sum up the operations

   All steps are linear scans or swaps, so total time complexity is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No sorting or factorial generation involved, linear scans only [OK]

Hint: Next permutation scans array linearly multiple times [OK]

Common Mistakes:

• Confusing suffix reversal with sorting
• Assuming factorial due to permutations

4. Consider the following buggy implementation of next permutation. Which line contains the subtle bug that causes incorrect output when the input array is in descending order?

medium

A. Line 5: if i >= 0:

B. Line 13-16: reversing the suffix after pivot

C. Line 10: nums[i], nums[j] = nums[j], nums[i]

D. Line 2: while i >= 0 and nums[i] >= nums[i + 1]: i -= 1

Solution

1. Step 1: Identify the bug

   The comment indicates the reversal of the suffix is missing or incorrectly implemented, which is critical when the array is descending (no pivot found).

2. Step 2: Analyze the reversal code

   The reversal loop runs regardless of whether i is -1, which causes incorrect behavior when the entire array is descending; the suffix should be reversed to the lowest permutation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing or incorrect suffix reversal causes wrong output on descending arrays [OK]

Hint: Suffix reversal must always happen after pivot swap or when no pivot found [OK]

Common Mistakes:

• Not reversing suffix after swap
• Swapping with wrong element
• Ignoring descending array edge case

5. Suppose the problem is modified so that numbers can be reused multiple times in the arrangement. Which change to the backtracking algorithm correctly adapts to this variant?

hard

A. Keep the 'used' bitmask but reset bits after each recursive call to allow reuse.

B. Remove the 'used' bitmask and allow all numbers at every position, checking divisibility only.

C. Use a frequency array to track counts of each number and decrement/increment during recursion.

D. Modify the divisibility condition to allow partial matches and keep the bitmask unchanged.

Solution

1. Step 1: Understand reuse implication

   Allowing reuse means numbers are no longer unique per position, so tracking used numbers is unnecessary.

2. Step 2: Adapt algorithm

   Removing the 'used' bitmask and checking only divisibility conditions at each position correctly counts valid arrangements with reuse.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without uniqueness constraint, 'used' tracking is redundant [OK]

Hint: Reuse means no need to track used numbers [OK]

Common Mistakes:

• Trying to reset bitmask bits incorrectly
• Using frequency arrays unnecessarily