LeetCode Entry

1688. Count of Matches in Tournament

05.12.2023 easy 2023 kotlin

Count of odd-even matches according to the rules x/2 or 1+(x-1)/2.

1688. Count of Matches in Tournament easy blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/428

Problem TLDR

Count of odd-even matches according to the rules x/2 or 1+(x-1)/2.

Intuition

The naive solution is to just implement what is asked.

Approach

Then you go read others people solutions and found this: n-1.

Complexity

  • Time complexity: \(O(log(n))\)

  • Space complexity: \(O(1)\)

Code


  fun numberOfMatches(n: Int): Int {
    var x = n
    var matches = 0
    while (x > 1) {
      if (x % 2 == 0) {
        matches += x / 2
        x = x / 2
      } else {
        matches += (x - 1) / 2
        x = 1 + (x - 1) / 2
      }
    }
    return matches
  }