There is a task: there is a number of boys who want to fight, if number is even, they divide into pairs and who lost - goes home. And they divide into pairs, fight and someone goes home until they get odd number of people. And when finally odd number of people left - everyone fights with every possible enemy. Formula looks like: n(n-1)/2. For example 5 guys - 10 fights.

If the number of guys from the very beginning is odd - the same way of counting: n(n-1)/2.

I've wrote script that counts all possible number of fights, smth like this:

function qwe(number) {
        if(number % 2) {
            return number = number*(number-1)/2
        } else {
            number = number / 2; 
            return number   qwe(number)
        }
    }
    
console.log(qwe(6));

But what to do if I know number of fights and want to know how many people I need for this fightings? How to execute this function in the opposite way?

CodePudding user response：

You cannot easily reverse this function, at least not entirely.

With three fighters, there will be 3 * (3 - 1) / 2, or 3 fights. With four fighters, there will be 2 fights in the first round and then 1 in the second, for 3 fights. So if we know there are three fights, we don't know if there are three or four fighters. Similarly, qwe (10) is 15 and so is qwe (16).

It's possible -- and in fact it seems likely from my tests (up to n of 1000000) that there are at most two inputs to yield any given output.

We can find them all through exhaustive search, because it's easy to show that qwe (n) is always at least n - 1, so if we check the answers for all values up to one more than our target, we will have found all those that hit the target. But with a function as chaotic as this, I have a hard time seeing how to improve that exhaustive search. We can easily test the odd-number results, since qwe (n) = n * (n - 1) / 2 and through some simple algebra, we can demonstrate that if qwe (n) == t, then n = (1 sqrt (1 8 * t)) / 2, but testing the recursive step seems much more problematic.