Got a question in interview, find most divisible by other numbers in the array, say [2,4,8], 8 is able to be divided by 3 numbers, and that is the ans. I have a O(N^2) solution, but is there a better solution than O(N^2)?
I think, something like quick sort will make sense, but not yet get the solution, like if a % b, b%c => a%c, but % operation is not transitional like > operation.
You can work with trees with O(NlogN).
The fastest algorithm i think is to make a heap (AVL tree is the best choice) tree with this rule:
For input x: find x%node[i] == 0 or node[i]%x == 0
If you found this node add x to node[i]'s children collection or replace Node[i] with x and add Node[i] to x's Children Collection.
else add this node to the root Node.