tag

#fractions

2 pages tagged

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 972: Equal Rational Numbers

Problem Restatement We are given two strings s and t . Each string represents a non-negative rational number. A number may be written in one of these forms: "123" "123.456" "123.456(789)" Parentheses mark the repeating decimal part. Return true if both strings represent the same rational number. Otherwise, return false . Examples of equivalent forms: "0.1(6)" == "0.1666(6)" "0.9(9)" == "1." The official note says the integer part length is...

Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Kth Smallest Fraction

Kth Smallest Fraction Kth Smallest Fraction selects the k-th smallest value among fractions of the form: $$ \frac{A[i]}{A[j]} $$ where the array $A$ is sorted and: $$ 0 \le i < j < n $$ This problem appears in number theory and ranking problems. Direct enumeration gives $O(n^2)$ fractions, which is too large. Problem Given a sorted array $A$ of positive integers and an integer $k$, return the k-th smallest...