Frontend School

K-Smooth Factorial Numbers

DSA
medium

K-Smooth Factorial Numbers

Medium
Math
Number Theory
Algorithms
BigInt

Overview

In the realm of distributed systems and resource allocation, unique identifiers and resource scheduling often rely on sequences of numbers with specific mathematical properties. For instance, certain cryptographic protocols or distributed ledger systems might require numbers whose prime factors are constrained to a small set, ensuring predictable computational costs for factorization or modular arithmetic. This problem explores such a sequence, combining concepts of prime factorization and factorials, to identify numbers suitable for specific system-level applications.

What you need to do / Task

Your task is to implement a function findKthSmoothFactorial that determines the N-th positive integer X conforming to the following criteria:

  1. K-Smooth Property: All prime factors of X are less than or equal to a given integer K.
  2. Factorial Divisibility: X must be a multiple of K! (K factorial).

The sequence of such numbers X should be strictly increasing. You need to find the N-th number in this ordered sequence.

Input & output

Function Signature: function findKthSmoothFactorial(K: number, N: number): bigint (TypeScript) function findKthSmoothFactorial(K, N) (JavaScript)

Parameters:

  • K: A positive integer representing the upper bound for prime factors and the base for the factorial. (2 <= K <= 10)
  • N: A positive integer representing the index of the number to find in the sorted sequence. (1 <= N <= 1000)

Return Value:

  • A bigint (TypeScript) or a BigInt (JavaScript) representing the N-th K-Smooth Factorial Number.

Clarifications

  • The sequence of K-Smooth Factorial Numbers starts with the smallest such number and is strictly increasing.
  • K! denotes K factorial (e.g., 5! = 5 * 4 * 3 * 2 * 1 = 120).
  • The problem requires handling potentially very large numbers, so BigInt in JavaScript/TypeScript is necessary for calculations and the return value. Do not use standard number for intermediate or final results that might exceed Number.MAX_SAFE_INTEGER.
  • For K=2, the allowed prime factors are just {2}. 2! = 2. The sequence of 2-Smooth Factorial Numbers is 2, 4, 8, 16, ... (i.e., 2^1, 2^2, 2^3, ...).

Examples

1

Example 1

Input:

K = 3, N = 4

Output:

24n

Note:

For K=3, the allowed prime factors are {2, 3}. K! = 3! = 6. Numbers with only prime factors 2 and 3: 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, ... Filtering for multiples of 6: 6, 12, 18, 24, 36, ... The 4th number in this sequence is 24.

2

Example 2

Input:

K = 2, N = 3

Output:

8n

Note:

For K=2, the allowed prime factors are {2}. K! = 2! = 2. Numbers with only prime factor 2: 1, 2, 4, 8, 16, ... Filtering for multiples of 2: 2, 4, 8, 16, ... (Note: 1 is not a multiple of 2). The 3rd number in this sequence is 8.

3

Example 3

Input:

K = 5, N = 10

Output:

1440n

Note:

For K=5, the allowed prime factors are {2, 3, 5}. K! = 5! = 120. The problem is equivalent to finding the N-th number X such that X = Y * K!, where Y is a K-smooth number (i.e., Y's prime factors are only from {2,3,5}). The first few K-smooth numbers (for primes {2,3,5}) are: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ... The 10th such Y is 12. Therefore, the 10th K-Smooth Factorial Number is 12 * 120 = 1440.

Constraints

Constraints & assumptions

  • 2 <= K <= 10
  • 1 <= N <= 1000
  • The final result and intermediate calculations involving the sequence numbers may exceed the maximum safe integer for standard JavaScript number type. Use BigInt for all such computations.
  • Time complexity: Aim for an efficient solution, ideally better than exponential in K or N. A solution with polynomial time complexity in N and K is expected.
  • Space complexity: Should be reasonable, proportional to N and K.

Out of scope

  • Input validation (e.g., K or N being negative, non-integer, or outside specified bounds). Assume valid inputs.
  • Error handling for BigInt operations.

What interviewers evaluate

  • Correctness: The solution must accurately identify the N-th K-Smooth Factorial Number for all valid inputs.
  • Algorithmic Efficiency: Demonstrated understanding and application of efficient algorithms for prime generation (e.g., Sieve of Eratosthenes) and sequence generation (e.g., optimized ugly number generation).
  • Edge Case Handling: Correctly handles smaller K values (e.g., K=2, K=3) and N=1.
  • Large Number Management: Proper use of BigInt to handle values exceeding standard integer limits.
  • Code Quality: Clean, readable, well-structured code with appropriate data structures and comments where necessary.

Loading editor...