K-th Smallest Prime Fraction
MediumAsked by:
+1
More companies
25 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 kth 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 <= 10001 <= arr[i] <= 3 * 104arr[0] == 1arr[i]is a prime number fori > 0.- All the numbers of
arrare unique and sorted in strictly increasing order. 1 <= k <= arr.length * (arr.length - 1) / 2
O(n2) complexity?
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. |
Empty array or null array
How to Handle:
Return null or throw an IllegalArgumentException as there are no fractions.
Array with a single prime number
How to Handle:
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)
How to Handle:
Return null or throw an IllegalArgumentException as K is out of bounds.
Large array size leading to potential memory issues or slow runtime (scalability)
How to Handle:
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)
How to Handle:
Use long data type to avoid overflow issues during the calculation of fractions.
Duplicate prime numbers in the input array
How to Handle:
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)
How to Handle:
Binary search will still find *a* fraction equal to the kth smallest, regardless of duplicates.
Floating point precision issues when comparing fractions
How to Handle:
Compare fractions using a small epsilon value to account for potential precision errors.
Explore Interview QuestionsTaro 75Google Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Interview ExperiencesOpenAI Interview ExperiencesAnthropic Interview ExperiencesPerplexity Interview ExperiencesWindsurf Interview ExperiencesMistral AI Interview Experiences
