One task on litcode
Sometimes you want to solve a problem simply because the solution is easy to check, right away for a lot of options. We took a list of 25 elements, sorted it, and applied the desired function 25 times, profit. Plus, the problem resembles the cover of a notebook on arithmetic for the fifth grade, where there is a plate of products, well, the one where we find the fifth column and the seventh row and there will be a product at their intersections. In the same place, the plate shows that 6×6 is a square, and 9×4 is not a square at all (rather closer to a rectangle), although their area is equal. So, “litcode” wants us to find the nth element in the given plate in ascending order.
One of the possible solutions is to collect the elements in a list, sort it, take the nth element, profit (just in case, do not forget about the select_nth_unstable algorithm in growth). Unfortunately, there are a lot of elements in the tablet, so it is more interesting to collect only a part of the elements. After meditating a little over the tablet (https://ru.wikipedia.org/wiki/Multiplication_table) it is better to break it into groups (as shown below) and only then collect and select an element. Group criterion – all elements are less than or equal to the far right (please see the figure below).
1 2 3 4 5
2 4 * * *
3 * * * *
4 * * * *
5 * * * *
- - - - -
- - 6 8 10
- 6 9 * *
- 8 * * *
- 10 * * *
- - - - -
- - - - -
- - - 12 15
- - 12 * *
- - 15 * *
- - - - -
- - - - -
- - - - -
- - - 16 20
- - - 20 *
- - - - -
- - - - -
- - - - -
- - - - -
- - - - 25
The principle of dividing into groups seems to be reminiscent of https://ru.wikipedia.org/wiki/Harmonic_series, which seems to be a good sign 🙂 So, now the partition itself: we take the first row from the plate as a whole, the first half from the second row, the first third from the third row, etc. For the second iteration – the second half of the second row, then the second third of the third, the second quarter, etc. That is, if the plate is 10×10, for the third row the partition is 3,3,4 by elements for the first, second and third iteration; for the fourth row 2,3,2,3 – for four iterations, respectively. Another point, for each iteration, the number of elements in the group is different. For example, for the plate from the figure above in the first iteration 5+2+1+1+1=10 elements, for the second iteration 3+2+1+1=7.
To find the 20th element in a 5×5 table, we take the third group, since the first group has 10 elements, the second has 7, the third has 4; that is, we add the deltas until the sum exceeds the desired index. Sounds OK, but it’s slow – because the delta is different and, as a result, a linear search.
For binary search, it would be nice to go from deltas 10,7,4,3,1 to half-sums 10, 17, 21, 24, 25. Each row of the tablet participates in several groups, for example, the third row – in the first three groups, the fourth – in four groups. For the third row, the partition is 1,2,2 by the number of elements, for the fourth, 1,1,1,2. A little more detailed – for the 5×5 tablet and the third row, we divide five by three and transfer the remainder of the division to the next step. To get to half-sums, for each step of dividing by three, let’s multiply five by i (step number), that is, we get (5/3, 10/3, 15/3 -> 1,3,5, that is, our half-sums. Once again for comparison it was-> became: (5/3, {5+r}/3, {5+r2}/3) or 1,2,2 -> (5/3, 10/3, 15/3) or 1,3,5 We collect half-sums of rows in a group, profit.The rest is implementation details.
Probably the main point of the article is in the transition from linear to binary search. Just in case, for a billion elements, binary search does 30 checks, linear search does about 2**30. Thank you for your attention.
