Given a large number, n, find all positive numbers less than or equal to n that can be represented as the sum of two cubes for at least two different pairs. In other words, find all positive numbers m <=> that can be expressed as: m = (a3 + b3) = (c3 + d3) for distinct a, b, c, d. If n = 25000, m can be any of 1729, 4104, 13832, or 20683 as these numbers can be represented as the sum of two cubes for two different pairs.
1729 = 13 + 123 = 93 + 103 Practice this problem The idea is simple. We know that any number m that satisfies the constraint will have two distinct pairs (let's say (a, b) and (c, d)). Since m < n, we can say that a, b, c, and d are less than n1/3. Now for every distinct pair (x, y) formed by numbers less than the n1/3, store their sum x3 + y3 into a set. If two pairs with the same sum exist, print the sum. Following is the C++, Java, and Python implementation of the idea:
Download Run Code Output:
Download Run Code Output:
Download Run Code Output: 20683 The time complexity of the above solution is O(n2/3).
Thanks for reading. Please use our online compiler to post code in comments using C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages. Like us? Refer us to your friends and help us grow. Happy coding đ |