K-th Smallest Prime Fraction

Medium

Asked by:

+1

More companies

16 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:

16 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 bounds on the length of the input array `arr` and the value of `k`?
Are the elements in the input array `arr` guaranteed to be unique and in ascending order?
Is `k` guaranteed to be a valid value, meaning is it always within the possible number of fractions that can be formed from `arr`?
Should the returned fraction be an array of two integers representing the numerator and denominator, or can it be a floating point number?
If there are multiple fractions that qualify as the k-th smallest, can I return any one of them?

Brute Force Solution

Approach

The goal is to find the K-th smallest fraction made from a given list of prime numbers. The brute force approach is simply to generate all possible fractions, sort them, and then pick the K-th one.

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

First, create all possible fractions using the given list of prime numbers. Each fraction will have one prime number as the top part (numerator) and another prime number as the bottom part (denominator).
Make sure the top part is always smaller than the bottom part, because we only want fractions that are less than 1.
Now, we have a big list of all the possible fractions. Sort this list from smallest to largest.
Finally, find the fraction at the K-th position in the sorted list. That's the K-th smallest fraction.

Code Implementation

def kth_smallest_prime_fraction_brute_force(primes, k):
    fractions = []

    # Create all possible fractions (p1 / p2) where p1 < p2.
    for numerator_index in range(len(primes)): 
        for denominator_index in range(len(primes)):
            if primes[numerator_index] < primes[denominator_index]:
                fractions.append((primes[numerator_index] / primes[denominator_index], primes[numerator_index], primes[denominator_index]))

    # Sort the fractions based on their values.
    fractions.sort(key=lambda x: x[0])

    # Return the K-th smallest fraction.
    return [fractions[k - 1][1], fractions[k - 1][2]]

Big(O) Analysis

Time Complexity

O(n² log n) – The algorithm first generates all possible fractions from the n prime numbers, resulting in approximately n * n/2 unique fractions since we consider only pairs where the numerator is smaller than the denominator. This fraction generation takes O(n²) time. Next, these fractions are sorted using a comparison-based sorting algorithm, which typically has a time complexity of O(m log m), where m is the number of fractions. Since m is approximately n²/2, the sorting step takes O(n² log n²) which simplifies to O(n² log n). Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n² log n).

Space Complexity

O(N^2) – The brute force approach described constructs all possible fractions where the numerator and denominator are elements from the input array of size N. This results in a list of approximately N * N or N^2 fractions. Storing this list of fractions requires auxiliary space proportional to the number of fractions. Sorting the list in place may not change the overall auxiliary space, and depending on the sorting algorithm, could require additional space, but the primary space usage is due to the list of generated fractions. Therefore, the auxiliary space complexity is O(N^2).

Optimal Solution

Approach

We're looking for the K-th smallest fraction made from a given list of prime numbers. Instead of checking all possible fractions, we can use a method to quickly narrow down the possibilities until we find the fraction we need.

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

Imagine all the possible fractions are organized from smallest to largest, though we don't actually build that entire list.
Use a process like guessing a number and checking if it's too high or too low. Start with a guess for the fraction's value.
Count how many actual fractions from our list are smaller than this guess.
If the count is less than K, our guess was too low. We need to guess higher.
If the count is greater than or equal to K, our guess was too high. We need to guess lower.
Keep adjusting our guess up or down until we find the exact fraction where there are exactly K-1 fractions smaller than it.
The final guess that meets the requirement is the K-th smallest fraction.

Code Implementation

def kth_smallest_prime_fraction(primes, k):
    low_value = 0.0
    high_value = 1.0

    while low_value < high_value:
        mid_value = (low_value + high_value) / 2.0
        count = 0
        max_fraction = 0.0
        index_i = 0

        # Count fractions <= mid_value and track the largest.
        for index_j in range(1, len(primes)):
            while primes[index_i] / primes[index_j] <= mid_value:
                index_i += 1
                if index_i == len(primes):
                    break

            count += index_i
            if index_i > 0:
                max_fraction = max(max_fraction, primes[index_i - 1] / primes[index_j])

        # Adjust search range based on the count.
        if count == k:
            return [primes[int(max_fraction * primes[index_j -1 ])], primes[index_j]]

        if count < k:
            low_value = mid_value
        else:
            high_value = mid_value

    numerator = 0
    denominator = 1
    return [numerator, denominator]

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm performs a binary search to find the K-th smallest fraction. The search space is between 0 and 1. For each guess in the binary search, we iterate through the array of prime numbers (of size n) to count the number of fractions smaller than the guess. The counting process involves another nested loop that on average iterates through n elements. The binary search takes log(range) steps where range can be bound by 1, a constant. Therefore, the time complexity is dominated by the n*n operations inside the binary search, performed log n times. Overall giving a time complexity of O(n log n) approximately.

Space Complexity

O(1) – The described algorithm focuses on adjusting a guess and counting fractions smaller than that guess. It doesn't mention creating any auxiliary data structures like lists, hash maps, or trees to store intermediate values or previously visited states. The operations involve counting and comparing, suggesting the use of a few constant-sized variables to track the count, the guess, and potentially loop indices. Therefore, the auxiliary space used remains constant regardless of the input size N (the number of prime numbers).

Edge Cases

Case	How to Handle
Empty array or null array	Return null or throw an IllegalArgumentException as there are no fractions.
Array with a single prime number	Return null or throw an IllegalArgumentException as a fraction requires two numbers.
K is less than 1 or greater than the total number of possible fractions (n*(n-1)/2)	Return null or throw an IllegalArgumentException as K is out of bounds.
Large array size leading to potential memory issues or slow runtime (scalability)	Use a heap-based approach that avoids generating all possible fractions upfront for better memory efficiency.
Prime numbers leading to potential integer overflow during calculation (numerator/denominator)	Use long data type to avoid overflow issues during the calculation of fractions.
Duplicate prime numbers in the input array	The algorithm should inherently handle duplicates as fractions are based on index pairs.
Kth fraction has multiple identical values (e.g., multiple pairs resulting in the same fraction)	Binary search will still find a fraction equal to the kth smallest, regardless of duplicates.
Floating point precision issues when comparing fractions	Compare fractions using a small epsilon value to account for potential precision errors.