Skip to content

2509. Cycle Length Queries in a Tree 👍

  • Time: $O(q\log n)$
  • Space: $O(q)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  vector<int> cycleLengthQueries(int n, vector<vector<int>>& queries) {
    vector<int> ans;

    for (const vector<int>& query : queries) {
      ans.push_back(1);
      int a = query[0];
      int b = query[1];
      while (a != b) {
        if (a > b)
          a /= 2;
        else
          b /= 2;
        ++ans.back();
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int[] cycleLengthQueries(int n, int[][] queries) {
    int[] ans = new int[queries.length];

    for (int i = 0; i < queries.length; ++i) {
      ++ans[i];
      int a = queries[i][0];
      int b = queries[i][1];
      while (a != b) {
        if (a > b)
          a /= 2;
        else
          b /= 2;
        ++ans[i];
      }
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:
    def getCycleLength(a: int, b: int):
      cycleLength = 1
      while a != b:
        if a > b:
          a //= 2
        else:
          b //= 2
        cycleLength += 1
      return cycleLength

    return [getCycleLength(*query) for query in queries]