I have to find a solution for this equation:
I have to find the set of solutions a, b, c, d for all possible combinations of values 1 <= x <= n.
$a^5 + b^5 = c^5 + d ^ 5$
I first thought about using a heap, because it is what I am learning, but I can't seem to come up with a pattern.
I was told that my algorithm should run in $O(n^2\log(n))$ so I know I would have to use a heap of size n, with n*2 inserts into its structure.
That's as far as I got, can someone hint me?
You can generate all possible triples $(x^5 + y^5, x, y): x, y \in \{1, \dots, n\}$. There are $n^2$ of them. Next you can sort them by first component using heap sort or any other sorting algorithm(it will take $\mathcal{O}(n^2\cdot\log_2(n))$). Now we have $k$ subsequences in sorted sequence where all triples have equal first component. Let's denote $i$th subsequence as $S_i$ and their first component as $c_i$. Each $S_i$ gives $\frac{|S_i| \cdot (|S_i|-1)}{2}$ solutions such that $a^5 + b^5 = c_i = c^5 + d^5$. Number of solutions is $\mathcal{O}(|S_1|^2) + \cdots + \mathcal{O}(|S_k|^2) = \mathcal{O}(n^2)$ since $|S_1| + \cdots + |S_k| = n$.
You also can just build heap on the sequence of all triples. And consequentially extract triples with minimum first component from it. While triples have equal first component they are part of some subsequence $S_i$.
To build heap of size $n^2$ we need $\mathcal{O}(n^2)$ and to extract $n^2$ times minimum from it we need $\mathcal{O}(n^2\cdot\log_2(n))$.
