I've been thinking that I found solution, but tests fail (I have no access to tests).
The task:
We want to organize a chess tournament.
One day - one game.
And as entry point we have number of days - that we can afford.
Tournament rules:
We have number of teams: if number is even - we divide number of teams by 2 and that's the number of games - so they fight 1 vs 1 in pairs, who lost is excluded from the competition.
For example : 20 teams => 10 games => 10 teams left.
And if the even number of teams left - we make the same iteration: divide by 2 into pairs.
10 teams - 5 games - 5 teams left.
And now we have Odd number!
If we have odd number from start or get it in process - number of games is counted by another rule:
everyone needs to play with everyone. So the formula is = n * (n-1) / 2.
For example 5 teams = 10 games.
Or any odd number (to sum it all - if we have Odd number we always ignore first rule with pairs).
So:
We have number of days and need to find all possible team numbers for this days, it can be more than one value, for example : 3 days, number of teams that is correct is 3 and 4;
Entry point 3, function logs 3 and 4;
If that's impossible to find teams - return -1;
1 ≤ 𝑁 ≤ 1000000
Here is my solution - It ouputs correct values, but tests fail Can someone help to find what I did wrong? (Sorry for code mess, I had different thoughts every time)
function solve(input) {
let quadraticEquation = (number) => {
let a = 1;
let b = -1;
let c = -number*2
if(a == 0)
return 'false';
let res = {};
let D = b * b - 4 * a * c;
let tmp = [];
if(D < 0)
return 'false';
res['discriminant'] = D;
if(D == 0)
res["quadratic roots"] = (-b + Math.sqrt(D)) / (2 * a);
else if(D > 0){
tmp.push((-b + Math.sqrt(D)) / (2 * a));
tmp.push((-b - Math.sqrt(D)) / (2 * a));
res["quadratic roots"] = tmp;
}
return tmp;
}
let start = input;
let xValues = quadraticEquation(start).map(item => Math.abs(item)).filter(item => item % 2 !== 0);
let arrayToUse = []
for(i = 0; i <= xValues[xValues.length-1]; i++) {
if( i === 1) {
continue;
}
if (!(i%2)) {
continue
}
arrayToUse.push(i);
}
const answer = [];
arrayToUse.forEach(item => {
let startValue = item;
let fightsNumber = item * (item - 1) / 2;
let loop = 0;
if (fightsNumber === start) {
answer.push([startValue, loop])
} else {
do {
loop++;
fightsNumber += startValue;
if (fightsNumber === start) {
answer.push([item, loop] )
}
startValue *= 2;
} while (fightsNumber < start)
}
})
function getTeams (answer) {
const finalResult = [];
answer.forEach(item => {
if(item[1] === 0) {
finalResult.push(item[0]);
} else {
let initialValue = item[0];
for(i=0; i < item[1]; i++) {
initialValue += item[0];
item[0] *= 2;
}
finalResult.push(initialValue);
}
})
let initialValue = 2;
let fightCounter = 0;
for (i = 0; i <= start; i++) {
fightCounter += initialValue / 2
if (fightCounter === start) {
finalResult.push(initialValue);
}
initialValue *= 2;
}
return finalResult;
}
let finalString = ''
const arrayToLog = getTeams(answer).sort((a,b) => a - b);
if(arrayToLog.length !== 0) {
arrayToLog.forEach(item => {
finalString += item + '\n';
})
} else {
finalString += -1;
}
return finalString;
}
console.log(solve(325))
console.log(solve(3))
console.log(solve(15))
console.log(solve(21))
console.log(solve(10))
console.log(solve(1))
console.log(solve(5))
console.log(solve(9))Note: for those who didn't see it, this is a followup to the earlier question Backward recurssion.
That's a lot of code for a fairly simple problem. I don't have the inclination or the time right now to go through it carefully.
So here is how I might solve this problem, using brute force to look for all the resulting number of days for any number of players up to days + 1, and then filtering out what we want from that list:
const range = (lo, hi) =>
[... Array (hi - lo + 1)] .map ((_, i) => i + lo)
const qwe = (n) =>
n % 2 == 1
? n * (n - 1) / 2
: n / 2 + qwe (n / 2)
const solve = (days) => {
const daysByPlayers = range (1, days + 1) .map (qwe)
const res = daysByPlayers .reduce ((a, d, i) => d == days ? [...a, i + 1] : a, [])
return res .length == 0 ? [-1] : res
}
const tests = [325, 3, 15, 21, 10, 1, 5, 9]
tests .forEach (n => console .log (`${n}: ${JSON.stringify(solve(n))}`)).as-console-wrapper {max-height: 100% !important; top: 0}This matches your output as far as I can tell. But I don't know what tests you say are failing, so perhaps there's something wrong with this as well.
There is extra complexity in here because of your desire for a -1 output in the missing cases. If an empty array would serve, then this is cleaner:
const solve = (days) =>
rng (1, days + 1) .map (qwe)
.reduce ((a, d, i) => d == days ? [...a, i + 1] : a, [])
And there are many variants. This one returns the maximum number of players that can be accommodated in some number of days up to the given value:
const solve = (days) => {
const daysByPlayers = rng (1, days + 1) .map (qwe)
const max = Math.max (... daysByPlayers .filter (d => d <= days))
return days - daysByPlayers .reverse () .indexOf (max) + 1
}
And this one gives you all the possible number of players available to achieve that maximum:
const solve = (days) => {
const daysByPlayers = rng (1, days + 1) .map (qwe)
const max = Math.max (... daysByPlayers .filter (d => d <= days))
return daysByPlayers .reduce ((a, d, i) => d == max ? [...a, i + 1] : a, [])
}
(For instance, solve (20) would return [10, 16], which are the possible number of players to handle in exactly 15 days, the largest value found no larger than 20.)
And finally, we could list all the numbers of players we could accommodate in up to a certain number of days:
const solve = (days) => {
const daysByPlayers = rng (1, days + 1) .map (qwe)
const max = Math.max (... daysByPlayers .filter (d => d <= days))
return daysByPlayers .reduce ((a, d, i) => d <= max ? [...a, i + 1] : a, [])
}
For instance, solve (20) would return [1, 2, 3, 4, 5, 6, 8, 10, 12, 16], which are the only numbers of players that could be handled in no more than 20 days.
When I brought up the quadratic formula in the earlier question it was just to note that in certain instances, we can find an exact solution, solving for d in n * (n - 1) / 2) = d. That meant that if 8 * d + 1 is a perfect square, then we can choose n to be (1 + sqrt (8 * d + 1)) / 2 to find one solution. But that's not of any real help in the general case.