Let’s look at a subset of inputs, and see what shakes out.

N.B. From problem description

– Phase 1: total of halves removed

– Phase 2 input: number of teams minus phase one

– Phase 2 output: phase-2-input * ( phase-2-input — 1 )/2

x (binary) phase-1 phase-2-input 1 (1b) = 0 1 3 (11b) = 0 3 5 (101b) = 0 5 7 (111b) = 0 7 9 (1001b) = 0 9 11 (1111b) = 0 11 x (binary) phase-1 phase-2-input 2 (10b) = 1 1 6 (110b) = 3 3 10 (1010b) = 5 5 14 (1110b) = 7 7 18 (10010b) = 9 9 22 (11110b) = 11 11 ... x (binary) phase-1 phase-2-input 8 (1000b) = 7 1 24 (11000b) = 21 3 40 (101000b) = 35 5 56 (111000b) = 49 7 72 (1001000b) = 63 9 88 (1111000b) = 77 11

First, notice the phase-2-input in each case: it’s strictly increasing. And phase-2-output (on this strictly increasing input) is strictly increasing. And phase 1 is strictly increasing too. Therefore, it’s safe to say that the total result on any series of inputs having the same number of ending-zeroes is strictly increasing.

This means we can perform a binary search on each group of partitioned inputs, for the given result. So, explicitly:

– Series 0: 1, 3, 5, 7… with no zeroes attached to the back

– Series 1: 1, 3, 5, 7… with 1 zero attached (yielding 2, 6, 10…)

– Series 2: 1, 3, 5, 7… with 2 zeroes attached

– etc.

Also notice that *any* number is part of *exactly one* series: if it ends in 1 zero it’s in series 1, ends in 14 zeroes it’s in series 14, etc. Therefore, all possible answers are searched.

(Also, notice the phase-1 to phase-2-input ratio in each series is the same. This is useful during implementation.)

With that, here it is in git and below: