Jobs

Interviews

Discussions

K-th Smallest Prime Fraction

Medium

Asked by:

More companies

26 views

Topics:

ArraysBinary Search

You are given a sorted integer array arr containing 1 and prime numbers, where all the integers of arr are unique. You are also given an integer k.

For every i and j where 0 <= i < j < arr.length, we consider the fraction arr[i] / arr[j].

Return the k^th smallest fraction considered. Return your answer as an array of integers of size 2, where answer[0] == arr[i] and answer[1] == arr[j].

Example 1:

Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

Example 2:

Input: arr = [1,7], k = 1
Output: [1,7]

Constraints:

2 <= arr.length <= 1000
1 <= arr[i] <= 3 * 10⁴
arr[0] == 1
arr[i] is a prime number for i > 0.
All the numbers of arr are unique and sorted in strictly increasing order.
1 <= k <= arr.length * (arr.length - 1) / 2

Follow up: Can you solve the problem with better than O(n²) complexity?

Try coding it in LeetCode

K-th Smallest Prime Fraction

Medium

Asked by:

26 views

Topics:

ArraysBinary Search

You are given a sorted integer array arr containing 1 and prime numbers, where all the integers of arr are unique. You are also given an integer k.

For every i and j where 0 <= i < j < arr.length, we consider the fraction arr[i] / arr[j].

Return the k^th smallest fraction considered. Return your answer as an array of integers of size 2, where answer[0] == arr[i] and answer[1] == arr[j].

Example 1:

Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

Example 2:

Input: arr = [1,7], k = 1
Output: [1,7]

Constraints:

2 <= arr.length <= 1000
1 <= arr[i] <= 3 * 10⁴
arr[0] == 1
arr[i] is a prime number for i > 0.
All the numbers of arr are unique and sorted in strictly increasing order.
1 <= k <= arr.length * (arr.length - 1) / 2

Follow up: Can you solve the problem with better than O(n²) complexity?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `arr` and the value of `k`? For example, what is the minimum and maximum number of elements in `arr`, and what is the range for `k`?
The problem states `arr` is a sorted list of prime numbers. Are we guaranteed that `arr` will always contain at least two elements to form at least one fraction, and are all elements in `arr` guaranteed to be positive primes?
The problem specifies finding the k-th smallest fraction. If there are multiple fractions with the same value, how should they be ordered to determine the k-th smallest? For instance, if we have 1/2 and 2/4 (which is also 1/2), how is their relative order determined?
What should be returned if `k` is larger than the total number of possible fractions that can be formed from `arr`? Or if `arr` has fewer than two elements?
Are there any implicit assumptions about the data types? For example, should I assume standard integer types, or are there possibilities for very large primes that might exceed typical integer limits for numerators and denominators?

Brute Force Solution

Approach

The problem asks us to find the K-th smallest fraction formed by picking two numbers from a given list. The brute force approach is to generate all possible fractions, sort them, and then pick the one at the K-th position.

Here's how the algorithm would work step-by-step:

Take every possible pair of numbers from the given list. For each pair, form a fraction by dividing the first number by the second number.
Collect all these fractions you just created.
Now, arrange all of the collected fractions in order from smallest to largest.
Once they are all sorted, count through them from the very smallest one.
Stop when you reach the K-th fraction in the sorted list. That fraction is your answer.

Code Implementation

def kthSmallestPrimeFraction(list_of_numbers, k_value):
    all_fractions = []

    # Generate all possible fractions from the given list
    for numerator_index in range(len(list_of_numbers)):
        for denominator_index in range(numerator_index + 1, len(list_of_numbers)):
            numerator_value = list_of_numbers[numerator_index]
            denominator_value = list_of_numbers[denominator_index]
            fraction_value = numerator_value / denominator_value
            all_fractions.append((fraction_value, numerator_value, denominator_value))

    # Sort all generated fractions to find the k-th smallest
    all_fractions.sort()

    # Return the k-th smallest fraction's numerator and denominator
    return [all_fractions[k_value - 1][1], all_fractions[k_value - 1][2]]

Big(O) Analysis

Time Complexity

O(n² log(n²)) – The brute force approach involves generating all possible fractions. If the input list has n numbers, there are n*(n-1)/2 possible pairs, leading to O(n²) fractions. Sorting these O(n²) fractions takes O(m log m) time, where m is the number of fractions, so it's O(n² log(n²)). Thus, the dominant operation is the sorting of all generated fractions.

Space Complexity

O(n^2) – The solution generates all possible fractions. If the input list has N numbers, there are N * (N-1) / 2 possible fractions. Storing all these fractions in a list or array requires auxiliary space proportional to the number of fractions, which is O(N^2). This list of fractions dominates the auxiliary space usage, leading to a space complexity of O(N^2).

Optimal Solution

Approach

We're looking for the k-th smallest fraction formed by pairs of numbers from a sorted list. Instead of generating and sorting all fractions, we can use a clever trick involving binary search to efficiently find the k-th smallest without checking every single one.

Here's how the algorithm would work step-by-step:

Imagine all possible fractions we can make from the given numbers, where the numerator is smaller than the denominator and both come from the list. We want to find the k-th smallest among these.
Think about the smallest possible value a fraction could have (close to zero) and the largest possible value (close to one). Our target fraction lies somewhere in this range.
We'll pick a 'midpoint' value within this range and check how many fractions are actually smaller than this midpoint.
To count these smaller fractions, we can go through the numbers and for each denominator, figure out how many numerators are smaller than our midpoint value times that denominator. This can be done efficiently because the list is sorted.
If the count of fractions smaller than our midpoint is less than 'k', it means our target k-th smallest fraction must be larger. So, we adjust our search range to the upper half.
If the count is 'k' or more, it means our target k-th smallest fraction is either our midpoint or smaller. We adjust our search range to the lower half and also remember the largest fraction we found that was still smaller than or equal to our current midpoint.
We keep repeating this process of picking a midpoint, counting, and adjusting our search range. With each step, the range gets smaller and smaller, homing in on the exact value of the k-th smallest fraction.
Eventually, our search range will become very, very small, and the largest fraction we recorded that was less than or equal to our best guess will be our answer.

Code Implementation

def kth_smallest_prime_fraction(list_of_prime_numbers, target_k):
    list_length = len(list_of_prime_numbers)
    low_bound_of_fraction = 0.0
    high_bound_of_fraction = 1.0
    best_numerator = 0
    best_denominator = 1

    while True:
        midpoint_fraction_value = (low_bound_of_fraction + high_bound_of_fraction) / 2.0
        count_of_smaller_fractions = 0
        current_best_numerator = 0

        # Optimize finding numerators for each denominator.
        right_pointer_index = 1
        for left_pointer_index in range(list_length - 1):
            while right_pointer_index < list_length and list_of_prime_numbers[left_pointer_index] > midpoint_fraction_value * list_of_prime_numbers[right_pointer_index]:
                right_pointer_index += 1
            count_of_smaller_fractions += (list_length - right_pointer_index)

            if right_pointer_index < list_length and list_of_prime_numbers[left_pointer_index] * best_denominator > list_of_prime_numbers[right_pointer_index] * best_numerator:
                best_numerator = list_of_prime_numbers[left_pointer_index]
                best_denominator = list_of_prime_numbers[right_pointer_index]

        # If the count matches k, we've found our fraction.
        if count_of_smaller_fractions == target_k:
            return [best_numerator, best_denominator]
        # If fewer than k fractions are smaller, we need to search higher.
        elif count_of_smaller_fractions < target_k:
            low_bound_of_fraction = midpoint_fraction_value
        # If k or more fractions are smaller, we can potentially search lower.
        else:
            high_bound_of_fraction = midpoint_fraction_value

Big(O) Analysis

Time Complexity

O(N * log(Range)) – The binary search operates on the range of possible fraction values, which is effectively constant (0 to 1). The crucial part is the check function within each binary search iteration. This check iterates through the array with a two-pointer approach (or a nested loop conceptually), taking O(N) time to count fractions smaller than the current midpoint. Since the binary search performs log(Range) iterations, and each iteration takes O(N) for the counting, the overall time complexity is O(N * log(Range)). Given the constant range, this simplifies to O(N) if we consider the binary search depth negligible, but more accurately it's driven by the O(N) counting step within each binary search iteration. The dominant factor becomes the linear scan within the binary search. However, the problem statement implies a more nuanced binary search, making the O(N * log(Range)) analysis more appropriate where Range is related to the precision needed. A more precise analysis considering the structure suggests O(N * log(1/epsilon)) where epsilon is the precision, or O(N * log(N^2)) if considering the number of fractions N^2, leading to O(N log N) for the check and then the binary search depth. The most common analysis based on the counting method within binary search is O(N * log(MaxVal)) where MaxVal is related to the magnitude of numbers, or more accurately, O(N * log(Range)). Considering the standard implementation and binary search over values, the count is O(N) and this is done within a binary search. The binary search depth is logarithmic in the range of possible fraction values. A common simplification leads to O(N * log(MaxNumber)) or O(N * log(Range)). A more precise analysis considering the number of fractions could lead to O(N log N), but the standard approach with binary search on values and O(N) counting step results in O(N * log(Range)).

Space Complexity

O(1) – The provided solution primarily uses a few variables to manage the binary search range (low, high), the count of fractions, and pointers for numerator and denominator. It also stores the best fraction found so far. No auxiliary data structures that grow with the input size N (number of elements in the sorted list) are created to store intermediate results or all possible fractions. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Input array `arr` is null or empty	The solution should explicitly check for null or empty `arr` and return an appropriate error or empty result to prevent crashes.
Input array `arr` has only one element	Since fractions require at least two distinct elements (numerator and denominator appearing later), an array with one element cannot form any valid fractions, and this case should be handled by returning an empty result.
Input `k` is less than 1	The problem implies k is 1-indexed, so k < 1 is an invalid input and should be handled with an error or specific return value.
Input `k` is greater than the total number of possible fractions	The solution needs to account for this by either returning the largest possible fraction or indicating that k is out of bounds, as there won't be a k-th smallest fraction.
All elements in `arr` are identical	If all prime numbers are the same, no valid fractions (where denominator appears later) can be formed, requiring a specific check for this scenario.
The input `arr` contains non-prime numbers	The problem statement specifies `arr` is a sorted list of prime numbers; if this constraint is violated, the behavior might be undefined or incorrect if the algorithm relies on primality.
Large `k` value and large `arr` size	An efficient solution, likely involving binary search on the fraction value or a min-heap, is necessary to handle large inputs within typical time limits.
Fractions result in very small or very large decimal values close to machine epsilon	Careful use of floating-point comparisons or an alternative approach that avoids direct float comparison (like fraction comparison using cross-multiplication) is essential to avoid precision errors.

Input array `arr` is null or empty

How to Handle:

The solution should explicitly check for null or empty `arr` and return an appropriate error or empty result to prevent crashes.

Input array `arr` has only one element

How to Handle:

Since fractions require at least two distinct elements (numerator and denominator appearing later), an array with one element cannot form any valid fractions, and this case should be handled by returning an empty result.

Input `k` is less than 1

How to Handle:

The problem implies k is 1-indexed, so k < 1 is an invalid input and should be handled with an error or specific return value.

Input `k` is greater than the total number of possible fractions

How to Handle:

The solution needs to account for this by either returning the largest possible fraction or indicating that k is out of bounds, as there won't be a k-th smallest fraction.

All elements in `arr` are identical

How to Handle:

If all prime numbers are the same, no valid fractions (where denominator appears later) can be formed, requiring a specific check for this scenario.

The input `arr` contains non-prime numbers

How to Handle:

The problem statement specifies `arr` is a sorted list of prime numbers; if this constraint is violated, the behavior might be undefined or incorrect if the algorithm relies on primality.

Large `k` value and large `arr` size

How to Handle:

An efficient solution, likely involving binary search on the fraction value or a min-heap, is necessary to handle large inputs within typical time limits.

Fractions result in very small or very large decimal values close to machine epsilon

How to Handle:

Careful use of floating-point comparisons or an alternative approach that avoids direct float comparison (like fraction comparison using cross-multiplication) is essential to avoid precision errors.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `arr` and the value of `k`? For example, what is the minimum and maximum number of elements in `arr`, and what is the range for `k`?
The problem states `arr` is a sorted list of prime numbers. Are we guaranteed that `arr` will always contain at least two elements to form at least one fraction, and are all elements in `arr` guaranteed to be positive primes?
The problem specifies finding the k-th smallest fraction. If there are multiple fractions with the same value, how should they be ordered to determine the k-th smallest? For instance, if we have 1/2 and 2/4 (which is also 1/2), how is their relative order determined?
What should be returned if `k` is larger than the total number of possible fractions that can be formed from `arr`? Or if `arr` has fewer than two elements?
Are there any implicit assumptions about the data types? For example, should I assume standard integer types, or are there possibilities for very large primes that might exceed typical integer limits for numerators and denominators?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take every possible pair of numbers from the given list. For each pair, form a fraction by dividing the first number by the second number.
Collect all these fractions you just created.
Now, arrange all of the collected fractions in order from smallest to largest.
Once they are all sorted, count through them from the very smallest one.
Stop when you reach the K-th fraction in the sorted list. That fraction is your answer.

Code Implementation

def kthSmallestPrimeFraction(list_of_numbers, k_value):
    all_fractions = []

    # Generate all possible fractions from the given list
    for numerator_index in range(len(list_of_numbers)):
        for denominator_index in range(numerator_index + 1, len(list_of_numbers)):
            numerator_value = list_of_numbers[numerator_index]
            denominator_value = list_of_numbers[denominator_index]
            fraction_value = numerator_value / denominator_value
            all_fractions.append((fraction_value, numerator_value, denominator_value))

    # Sort all generated fractions to find the k-th smallest
    all_fractions.sort()

    # Return the k-th smallest fraction's numerator and denominator
    return [all_fractions[k_value - 1][1], all_fractions[k_value - 1][2]]

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine all possible fractions we can make from the given numbers, where the numerator is smaller than the denominator and both come from the list. We want to find the k-th smallest among these.
Think about the smallest possible value a fraction could have (close to zero) and the largest possible value (close to one). Our target fraction lies somewhere in this range.
We'll pick a 'midpoint' value within this range and check how many fractions are actually smaller than this midpoint.
To count these smaller fractions, we can go through the numbers and for each denominator, figure out how many numerators are smaller than our midpoint value times that denominator. This can be done efficiently because the list is sorted.
If the count of fractions smaller than our midpoint is less than 'k', it means our target k-th smallest fraction must be larger. So, we adjust our search range to the upper half.
If the count is 'k' or more, it means our target k-th smallest fraction is either our midpoint or smaller. We adjust our search range to the lower half and also remember the largest fraction we found that was still smaller than or equal to our current midpoint.
We keep repeating this process of picking a midpoint, counting, and adjusting our search range. With each step, the range gets smaller and smaller, homing in on the exact value of the k-th smallest fraction.
Eventually, our search range will become very, very small, and the largest fraction we recorded that was less than or equal to our best guess will be our answer.

Code Implementation

def kth_smallest_prime_fraction(list_of_prime_numbers, target_k):
    list_length = len(list_of_prime_numbers)
    low_bound_of_fraction = 0.0
    high_bound_of_fraction = 1.0
    best_numerator = 0
    best_denominator = 1

    while True:
        midpoint_fraction_value = (low_bound_of_fraction + high_bound_of_fraction) / 2.0
        count_of_smaller_fractions = 0
        current_best_numerator = 0

        # Optimize finding numerators for each denominator.
        right_pointer_index = 1
        for left_pointer_index in range(list_length - 1):
            while right_pointer_index < list_length and list_of_prime_numbers[left_pointer_index] > midpoint_fraction_value * list_of_prime_numbers[right_pointer_index]:
                right_pointer_index += 1
            count_of_smaller_fractions += (list_length - right_pointer_index)

            if right_pointer_index < list_length and list_of_prime_numbers[left_pointer_index] * best_denominator > list_of_prime_numbers[right_pointer_index] * best_numerator:
                best_numerator = list_of_prime_numbers[left_pointer_index]
                best_denominator = list_of_prime_numbers[right_pointer_index]

        # If the count matches k, we've found our fraction.
        if count_of_smaller_fractions == target_k:
            return [best_numerator, best_denominator]
        # If fewer than k fractions are smaller, we need to search higher.
        elif count_of_smaller_fractions < target_k:
            low_bound_of_fraction = midpoint_fraction_value
        # If k or more fractions are smaller, we can potentially search lower.
        else:
            high_bound_of_fraction = midpoint_fraction_value

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input array `arr` is null or empty	The solution should explicitly check for null or empty `arr` and return an appropriate error or empty result to prevent crashes.
Input array `arr` has only one element	Since fractions require at least two distinct elements (numerator and denominator appearing later), an array with one element cannot form any valid fractions, and this case should be handled by returning an empty result.
Input `k` is less than 1	The problem implies k is 1-indexed, so k < 1 is an invalid input and should be handled with an error or specific return value.
Input `k` is greater than the total number of possible fractions	The solution needs to account for this by either returning the largest possible fraction or indicating that k is out of bounds, as there won't be a k-th smallest fraction.
All elements in `arr` are identical	If all prime numbers are the same, no valid fractions (where denominator appears later) can be formed, requiring a specific check for this scenario.
The input `arr` contains non-prime numbers	The problem statement specifies `arr` is a sorted list of prime numbers; if this constraint is violated, the behavior might be undefined or incorrect if the algorithm relies on primality.
Large `k` value and large `arr` size	An efficient solution, likely involving binary search on the fraction value or a min-heap, is necessary to handle large inputs within typical time limits.
Fractions result in very small or very large decimal values close to machine epsilon	Careful use of floating-point comparisons or an alternative approach that avoids direct float comparison (like fraction comparison using cross-multiplication) is essential to avoid precision errors.

Input array `arr` is null or empty

How to Handle:

The solution should explicitly check for null or empty `arr` and return an appropriate error or empty result to prevent crashes.

Input array `arr` has only one element

How to Handle:

Input `k` is less than 1

How to Handle:

The problem implies k is 1-indexed, so k < 1 is an invalid input and should be handled with an error or specific return value.

Input `k` is greater than the total number of possible fractions

How to Handle:

The solution needs to account for this by either returning the largest possible fraction or indicating that k is out of bounds, as there won't be a k-th smallest fraction.

All elements in `arr` are identical

How to Handle:

If all prime numbers are the same, no valid fractions (where denominator appears later) can be formed, requiring a specific check for this scenario.

The input `arr` contains non-prime numbers

How to Handle:

The problem statement specifies `arr` is a sorted list of prime numbers; if this constraint is violated, the behavior might be undefined or incorrect if the algorithm relies on primality.

Large `k` value and large `arr` size

How to Handle:

An efficient solution, likely involving binary search on the fraction value or a min-heap, is necessary to handle large inputs within typical time limits.

Fractions result in very small or very large decimal values close to machine epsilon

How to Handle:

Careful use of floating-point comparisons or an alternative approach that avoids direct float comparison (like fraction comparison using cross-multiplication) is essential to avoid precision errors.