We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Adjacent Swaps to Reach the Kth Smallest Number

Difficulty: Medium

Problem Description

You are given a string num, representing a large integer, and an integer k. We call some integer wonderful if it is a permutation of the digits in num and is greater in value than num. There can be many wonderful integers. However, we only care about the smallest-valued ones. Return the minimum number of adjacent digit swaps that needs to be applied to num to reach the kth smallest wonderful integer.

Key Insights

  • A wonderful integer is greater than the original number and is a permutation of its digits.
  • The goal is to find the kth smallest wonderful integer.
  • We can generate permutations in a sorted manner to find the kth smallest.
  • To determine the number of adjacent swaps needed, we can simulate the process of transforming the original number into the desired permutation.

Space and Time Complexity

Time Complexity: O(n^2) for generating the kth permutation and calculating adjacent swaps. Space Complexity: O(n) for storing the digits and permutations.

Solution

To solve this problem, we can use a combination of permutation generation and a greedy approach to count the minimum adjacent swaps required to transform the original number into the kth smallest wonderful integer. First, we will generate the permutations of the digits in sorted order until we reach the kth permutation. Then, we will calculate the number of adjacent swaps needed to convert the original string into this kth permutation.

  1. Generate all unique permutations of the digits in num.
  2. Sort the permutations to locate the kth smallest wonderful integer.
  3. Use a two-pointer technique or a simple greedy approach to count the minimum adjacent swaps needed to transform from num to the kth permutation.

Code Solutions

from itertools import permutations

def min_adjacent_swaps(num: str, k: int) -> int:
    # Generate all unique permutations of the digits in num.
    perm = sorted(set([''.join(p) for p in permutations(num)]))
    kth_permutation = perm[k - 1]  # Get the k-th smallest permutation.
    
    # Count the minimum adjacent swaps required to convert num to kth_permutation.
    return count_swaps(num, kth_permutation)

def count_swaps(num: str, target: str) -> int:
    num_list = list(num)
    target_list = list(target)
    swaps = 0
    
    for i in range(len(num_list)):
        if num_list[i] != target_list[i]:
            # Find the target character in the remaining list.
            target_index = i
            while num_list[target_index] != target_list[i]:
                target_index += 1
            
            # Perform adjacent swaps to move the target character to its position.
            while target_index > i:
                # Swap the characters.
                num_list[target_index], num_list[target_index - 1] = num_list[target_index - 1], num_list[target_index]
                target_index -= 1
                swaps += 1
                
    return swaps
← Back to All Questions