Given a number n, find two pairs that can represent the number as sum of two cubes. In other words, find two pairs (a, b) and (c, d) such that given number n can be expressed as
n = a^3 + b^3 = c^3 + d^3
where a, b, c and d are four distinct numbers.
Input: N = 1729 Output: (1, 12) and (9, 10) Explanation: 1729 = 1^3 + 12^3 = 9^3 + 10^3 Input: N = 4104 Output: (2, 16) and (9, 15) Explanation: 4104 = 2^3 + 16^3 = 9^3 + 15^3 Input: N = 13832 Output: (2, 24) and (18, 20) Explanation: 13832 = 2^3 + 24^3 = 18^3 + 20^3
Any number n that satisfies the constraint will have two distinct pairs (a, b) and (c, d) such that a, b, c and d are all less than n1/3. The idea is very simple. For every distinct pair (x, y) formed by numbers less than the n1/3, if their sum (x3 + y3) is equal to given number, we store them in a hash table using sum as a key. If pairs with sum equal to given number appears again, we simply print both pairs.
1) Create an empty hash map, say s. 2) cubeRoot = n1/3 3) for (int x = 1; x < cubeRoot; x++) for (int y = x + 1; y <= cubeRoot; y++) int sum = x3 + y3; if (sum != n) continue; if sum exists in s, we found two pairs with sum, print the pairs else insert pair(x, y) in s using sum as key
Below is C++ implementation of above idea –
(2, 24) and (18, 20)
Time Complexity of above solution is O(n2/3) which is much less than O(n).
Can we solve the above problem in O(n1/3) time? We will be discussing that in next post.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.