Integers With Multiple Sum of Two Cubes
Updated
Problem statement
Call an integer x good when it can be written as a^3 + b^3, with positive integers a <= b, in at least two different ways. Two ways are different when their pairs (a, b) are different.
For example, 1729 is good, because 1729 = 1^3 + 12^3 and also 1729 = 9^3 + 10^3.
Given an integer n, return every good integer x with x <= n, sorted from smallest to largest. Each good integer appears once. If there is none, return an empty list.
Function
findGoodIntegers(n: int) → List<Integer>Examples
Example 1
n = 4104return = [1729,4104]1729 = 1^3 + 12^3 = 9^3 + 10^3 and 4104 = 2^3 + 16^3 = 9^3 + 15^3. No other integer up to 4104 has two different pairs.
Example 2
n = 1728return = []1729 is the smallest good integer, so nothing up to 1728 is good.
Example 3
n = 20000return = [1729,4104,13832]The next good integer after 4104 is 13832 = 2^3 + 24^3 = 18^3 + 20^3. The one after that is 20683, which is larger than 20000.
Constraints
1 <= n <= 10^9
More Charta Health interview questions
Similar questions at other companies
- Top K Frequent WordsBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Financial Account LedgerStripe · OA · PHONE SCREENStripe interview questions
- Retrieve Vectors by Cosine SimilarityHarvey · ONSITE INTERVIEWHarvey interview questions
- Match Orders by Price and Arrival TimeAkuna Capital · OA · PHONE SCREEN · ONSITE INTERVIEWAkuna Capital interview questions
- Worst-Performing Ads by CTR in a Campaign TreeUber · PHONE SCREENUber interview questions
- Design Authentication ManagerOracle · ONSITE INTERVIEWOracle interview questions
- In-Memory Priority Task SchedulerRippling · PHONE SCREENRippling interview questions
- Balanced Session ManagerPalantir · PHONE SCREENPalantir interview questions
- Design a Food Rating SystemApple · PHONE SCREENApple interview questions
- Key-Value Store on a Block DeviceLambda · PHONE SCREEN