K Th Smallest In Lexicographical Order

                                            
class Solution {
public:
    int findKthNumber(int n, int k) {
        int curr = 1;
        k--;
        
        while (k > 0) {
            int steps = calculateSteps(n, curr, curr + 1);
            if (steps <= k) {
                curr++;
                k -= steps;
            } else {
                curr *= 10;
                k--;
            }
        }
        
        return curr;
    }
    
    int calculateSteps(int n, long n1, long n2) {
        int steps = 0;
        while (n1 <= n) {
            steps += min((long)n + 1, n2) - n1;
            n1 *= 10;
            n2 *= 10;
        }
        return steps;
    }
};

                                            
class Solution {
    public int findKthNumber(int n, int k) {
        int curr = 1;
        k = k - 1;

        while (k > 0) {
            int steps = calculateSteps(n, curr, curr + 1);
            if (steps <= k) {
                curr += 1;
                k -= steps;
            } else {
                curr *= 10;
                k -= 1;
            }
        }

        return curr;
    }

    private int calculateSteps(int n, long n1, long n2) {
        int steps = 0;
        while (n1 <= n) {
            steps += Math.min(n + 1, n2) - n1;
            n1 *= 10;
            n2 *= 10;
        }
        return steps;
    }
}

                                            
class Solution(object):
    def findKthNumber(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
        def count_steps(prefix, n):
            curr = prefix
            next = prefix + 1
            steps = 0
            while curr <= n:
                steps += min(n + 1, next) - curr
                curr *= 10
                next *= 10
            return steps
        
        prefix = 1
        k -= 1
        while k > 0:
            steps = count_steps(prefix, n)
            if steps <= k:
                prefix += 1
                k -= steps
            else:
                prefix *= 10
                k -= 1
        
        return prefix

                                            
int findKthNumber(int n, int k) {
    int curr = 1;
    k = k - 1;

    while (k > 0) {
        int steps = 0;
        long long first = curr;
        long long last = curr + 1;
        
        while (first <= n) {
            steps += fmin((long long)n + 1, last) - first;
            first *= 10;
            last *= 10;
        }
        
        if (steps <= k) {
            curr++;
            k -= steps;
        } else {
            curr *= 10;
            k--;
        }
    }
    
    return curr;
}

                                            
public class Solution {
    public int FindKthNumber(int n, int k) {
        int curr = 1;
        k = k - 1;

        while (k > 0) {
            long steps = getSteps(n, curr, curr + 1);
            if (steps <= k) {
                curr += 1;
                k -= (int)steps;
            } else {
                curr *= 10;
                k -= 1;
            }
        }

        return curr;
    }

    private long getSteps(int n, long n1, long n2) {
        long steps = 0;
        while (n1 <= n) {
            steps += Math.Min(n + 1, n2) - n1;
            n1 *= 10;
            n2 *= 10;
        }
        return steps;
    }
}

                                            
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var findKthNumber = function(n, k) {
    let cur = 1;
    k = k - 1;
    
    while (k > 0) {
        let steps = calculateSteps(n, cur, cur + 1);
        
        if (steps <= k) {
            k -= steps;
            cur += 1;
        } else {
            k -= 1;
            cur *= 10;
        }
    }
    
    return cur;
};

var calculateSteps = function(n, n1, n2) {
    let steps = 0;
    
    while (n1 <= n) {
        steps += Math.min(n + 1, n2) - n1;
        n1 *= 10;
        n2 *= 10;
    }
    
    return steps;
};

                                            
function findKthNumber(n: number, k: number): number {
    let curr = 1;
    k = k - 1;
    
    while (k > 0) {
        let steps = calculateSteps(n, curr, curr + 1);
        if (steps <= k) {
            curr += 1;
            k -= steps;
        } else {
            curr *= 10;
            k -= 1;
        }
    }
    
    return curr;
};

function calculateSteps(n: number, n1: number, n2: number): number {
    let steps = 0;
    
    while (n1 <= n) {
        steps += Math.min(n + 1, n2) - n1;
        n1 *= 10;
        n2 *= 10;
    }
    
    return steps;
}

                                            
class Solution {
    /**
     * @param Integer $n
     * @param Integer $k
     * @return Integer
     */
    function findKthNumber($n, $k) {
        $curr = 1;
        $k -= 1;
        while ($k > 0) {
            $steps = $this->calculateSteps($n, $curr, $curr + 1);
            if ($steps <= $k) {
                $curr += 1;
                $k -= $steps;
            } else {
                $curr *= 10;
                $k -= 1;
            }
        }
        return $curr;
    }

    private function calculateSteps($n, $n1, $n2) {
        $steps = 0;
        while ($n1 <= $n) {
            $steps += min($n + 1, $n2) - $n1;
            $n1 *= 10;
            $n2 *= 10;
        }
        return $steps;
    }
}

                                            
class Solution {
    func findKthNumber(_ n: Int, _ k: Int) -> Int {
        var cur = 1
        
        var k = k - 1
        
        while k > 0 {
            var steps = 0
            var first = cur
            var last = cur + 1
            while first <= n {
                steps += min(n + 1, last) - first
                first *= 10
                last *= 10
            }
            if steps <= k {
                cur += 1
                k -= steps
            } else {
                cur *= 10
                k -= 1
            }
        }
        
        return cur
    }
}

                                            
class Solution {
  int findKthNumber(int n, int k) {
    int result = 1;
    k--;
    
    while (k > 0) {
      int steps = countSteps(n, result, result + 1);
      if (steps <= k) {
        result += 1;
        k -= steps;
      } else {
        result *= 10;
        k -= 1;
      }
    }
    
    return result;
  }
  
  int countSteps(int n, int n1, int n2) {
    int steps = 0;
    
    while (n1 <= n) {
      steps += n + 1 - n1; // Made a slight change here
      n1 *= 10;
      n2 *= 10;
    }
    
    return steps;
  }
}

                                            
func findKthNumber(n int, k int) int {
    getCount := func(prefix int) int {
        count := 0
        cur, next := prefix, prefix+1
        for cur <= n {
            count += min(next, n+1) - cur
            cur *= 10
            next *= 10
        }
        return count
    }

    prefix := 1
    p := 1
    for p < k {
        count := getCount(prefix)
        if p+count > k {
            prefix *= 10
            p++
        } else {
            prefix++
            p += count
        }
    }

    return prefix
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

                                            
# @param {Integer} n
# @param {Integer} k
# @return {Integer}
def find_kth_number(n, k)
    cur = 1
    k -= 1
    while k > 0
        count = 0
        interval = [cur, cur + 1]
        while interval[0] <= n
            count += [n + 1, interval[1]].min - interval[0]
            interval = [interval[0]*10, interval[1]*10]
        end
        if count <= k
            cur += 1
            k -= count
        else
            cur *= 10
            k -= 1
        end
    end
    return cur
end

                                            
object Solution {
    def findKthNumber(n: Int, k: Int): Int = {
        def countPrefix(prefix: Long, n: Int): Int = {
            var count = 0
            var cur = prefix
            var next = prefix + 1

            while (cur <= n) {
                count += Math.min(n.toLong + 1, next).toInt - cur.toInt
                cur *= 10
                next *= 10
            }

            count
        }

        var kVal = k - 1
        var current = 1

        while (kVal > 0) {
            val steps = countPrefix(current.toLong, n)
            if (steps <= kVal) {
                current += 1
                kVal -= steps
            } else {
                current *= 10
                kVal -= 1
            }
        }

        current
    }
}

                                            
impl Solution {
    pub fn find_kth_number(n: i32, k: i32) -> i32 {
        let mut cur = 1;
        let mut k = k - 1;

        while k > 0 {
            let steps = Self::calculate_steps(n, cur as i64, (cur + 1) as i64);
            
            if steps <= k {
                cur += 1;
                k -= steps;
            } else {
                cur *= 10;
                k -= 1;
            }
        }

        cur as i32
    }

    fn calculate_steps(n: i32, n1: i64, n2: i64) -> i32 {
        let mut steps = 0;
        let mut n1 = n1;
        let mut n2 = n2;

        while n1 <= n as i64 {
            steps += i64::min(n as i64 + 1, n2) - n1;
            n1 *= 10;
            n2 *= 10;
        }

        steps as i32
    }
}

To solve this coding challenge, we need to find the k-th smallest lexicographical number in the range from 1 to n. Given the constraints that \( n \) can be as large as \( 10^9 \), a direct approach of generating and sorting all numbers up to \( n \) won't be efficient. Instead, we can use a more nuanced approach inspired by traversing a prefix tree (trie) to find the k-th number.

Explanation

The main idea is to iteratively find the prefix that matches the k-th smallest lexicographical number. The challenge can be broken down into the following steps:

Count the steps between prefixes : We need to count how many numbers exist between a given prefix and the next prefix in the lexicographical order. This helps in deciding whether the k-th number is within the current prefix block or if we should skip to the next prefix.
Iterate to find the correct prefix : Starting from the prefix
1

, iteratively determine whether to move to the next sibling prefix or go deeper into the current prefix.
Adjust k accordingly : Each time we know how many steps we've counted, update
k

to reflect the remaining steps.

Detailed Steps in Pseudocode

Define a helper function
count_steps(prefix, n)

that will count how many lexicographical numbers are there between the given prefix and the next prefix up to the boundary
n

.
Initialize the prefix with
1

and decrement
k

by 1 because we start counting from
1

.
Use a loop to continue adjusting the prefix until
k

reaches
0

.
Inside this loop, use the helper function to count the steps:

If the steps are less than or equal to
k

, that means the k-th number is not within the current prefix but further ahead. Move to the next sibling prefix and adjust
k

.
If the steps are more than
k

, that means the k-th number is within the current prefix. Move deeper into the prefix by multiplying it by
10

and decrementing
k

by
1

.

Return the correct prefix which now represents the k-th smallest number.

Pseudocode with Comments

                                            
Define function count_steps(prefix, n):
Initialize curr as prefix
Initialize next as prefix + 1
Initialize steps as 0

While curr <= n:
# Add the minimal steps between curr and next or limited by n+1
steps += min(n + 1, next) - curr

# Move to the next level in the lexicographical order
curr *= 10
next *= 10

Return steps

Define function find_kth_number(n, k):
Initialize prefix as 1
Decrement k by 1  # Because we start counting from 1

While k > 0:
steps = count_steps(prefix, n)

If steps <= k:
# k-th number is not in the current prefix range but further ahead
# Move to the next prefix sibling
prefix += 1
k -= steps
Else:
# k-th number is within the current prefix range
# Move deeper, go down to the next level with the current prefix
prefix *= 10
k -= 1

Return prefix

Step-by-Step Explanation

count_steps(prefix, n) :

This function calculates how many numbers exist between the given prefix and the next prefix up to
n

.
For example, if our prefix is
1

, this counts
1, 10, 100, ..., 19, 190, ..., 199

but not beyond
n

.

find_kth_number(n, k) :

Initialize
prefix

as
1

because this is the starting point.
Decrease
k

by 1 since the smallest number (starting point) is already considered part of the search.
Enter a loop to adjust the prefix until
k

becomes zero. During each iteration:

Use
count_steps

to understand the number of steps (numbers) available in the current prefix block.
If these steps are less than or equal to
k

, skip these steps as the k-th number is beyond this prefix, and update
prefix

to the next sibling. Adjust
k

by subtracting these steps.
If the steps are more than
k

, the k-th number lies within the current prefix -- go deeper into the prefix by multiplying it by
10

and decrement
k

by
1

reflecting the move downwards.

Once
k

is exhausted, the current prefix is the k-th smallest lexicographical number within the range from 1 to
n

.

This approach efficiently finds the k-th smallest number without generating and sorting all numbers. It leverages the structure of lexicographical rules to explore the number space systematically.