This is the ninth day of my participation in the First Challenge 2022

preface

Some people love each other, some people drive at night to watch the sea, some people can not solve the first question of Leetcode, so it can be seen that the question of Leetcode still has weight. Today we’re going to meet them

Subject to introduce

You are given an integer n for the number of teams in the game. The competition follows a unique format:

If the current number of teams is even, each team will be paired with another team. A total of N / 2 matches are played and n / 2 teams are generated to advance to the next round. If the current number of teams is odd, a random round will be played and one team will advance, and the remaining teams will be paired. A total of (n-1) / 2 matches are played and (n-1) / 2 + 1 teams are produced to advance to the next round. Returns the number of pairings made during the tournament until the winning team is determined. Example 1:

Input: n = 7 Output: 6 Explanation: Match Details: - Round 1: Number of teams = 7, Number of matches = 3, 4 teams advance. - Round 2: Number of teams = 4, number of matches = 2, 2 teams advance. - Round 3: Number of teams = 2, number of matches = 1, 1 winning team will be determined. Total number of pairs = 3 + 2 + 1 = 6Copy the code

Example 2:

Input: n = 14 Output: 13 Explanation: Match Details: - Round 1: Number of teams = 14, number of matches = 7, 7 teams advance. - Round 2: Number of teams = 7, number of matches = 3, 4 teams advance. - Round 3: Number of teams = 4, number of matches = 2, 2 teams advance. - Round 4: Number of teams = 2, number of matches = 1, 1 winning team will be determined. Total number of pairs = 7 + 3 + 2 + 1 = 13Copy the code

Tip:

1 <= n <= 200
Copy the code

mathematics

Train of thought

  • According to the title, there are two teams taking part in the competition
  • In every match one team will advance and one team will lose
  • In the end, only one team will win
  • Suppose you haveFour teamsSo the number of games isFirst couple and second teamPlay a game, the winning team andThe third teamPlay the game, the winning team of the second match andThe third teamTo compete for the championship, sofourThe teams compete altogether3 games
  • So,nOne team, you need to playn-1field

Method a

var numberOfMatches = function (n) {
    let res = 0
    while (n > 1) {
        res++
        n--
    }
    return res
};
Copy the code

Method 2

var numberOfMatches = function (n) {
    return n - 1
};
Copy the code

simulation

instructions

  • Simulate a real situation
  • Because we are not sure the number of cycles all useThe while loop
  • Each cycle (The game),
    • If the teams areAn even number, then proceedn/2Time matching
    • If the team isAn odd number“, then one of the teams will be empty, and then the number of matches will need to be(n-1)/2Time matching
    • And the number of teams left is(n-1)/2Add to that the empty teams, and the true remaining teams are(n-1)/2+1

solution

var numberOfMatches = function (n) { let res = 0 while (n > 1) { if (n % 2 === 0) { n /= 2 res += n } else { res += (n -  1) / 2 n = (n - 1) / 2 + 1 } } return res };Copy the code

Write in the last

  • I hope you find it rewarding