Binary search, Sorting, Hash table
You are given an array of heights of children h[1…n] and an integer F. If a child drops a ball from its height h[i], then it bounces back, to the height h[i] / F, falls down and bounces back again to the height h[i] / F^2 and so on. The task is to find the number of pair of students such that if the taller child drops a ball, it bounces back to the height of the second child after 0 or more bounces. If two children have equal height, then the pair is valid, because the ball reaches the height of the second child after 0 bounces and for each such pair you count it only once. In math words, the task is to find the number of pair of indices i, j such that h[i] < h[j] or h[i] = h[j] and i < j for which there exists a non-negative integer k such that h[j] / F^k = h[i].
There are at least two approaches differ by the underlying data structure.
You can sort array h in ascending order and then iterate over the array. For each element h[i] you divide it by F^0, F^1, … while F^k <= h[i] and for each of these divisions if its result is an integer, you use binary search to determine the number elements in h equal to the result.
The second approach uses a hash table t. Where t[i] is the number of elements in the array h with value i. Then you can use a similar approach to iterate over all elements and compute the result.
You can read more about hash tables here
You sort the array h in the ascending order at first. Then you iterate over elements of h. For each h[i], you compute h[i] / F^0, h[i] / F^1, … while F^k <= h[i] and for each of these values, if it is an integer d, you use binary search to determine the number of elements in h[1…i-1] with value d and add it to the result.
This method guarantees that you count a pair i, j only once if h[i] = h[j].
In c++ there is a handy method which can be used for computing the number of elements in h[1…i-1] equal to value d assuming that h is a vector:
Both these methods work in O(log n) time if the array is sorted.
O(n (log n)^2) because sorting takes O(n log n) and for each of n times in a loop we use binary search at most O(log n) times - once for each valid F^k.
For an approach which uses a hash table and described in quick explanation please look at the tester’s code.
For a partial credit, you can iterate over all pairs (i, j) and check if h[j] / F^k = h[i] for some k >=0 , where h[j] >= h[i]. This method works in O(n^2 * log 10^9) because there are O(n^2) pairs and for each pair we have to check at most log 10^9 values of k, because if h[i] = 10^9 and F = 2, then F^(log 10^9) = h[i].