DDSA Solutions

2509. Cycle Length Queries in a Tree

MediumView on LeetCode
TreeMathBinary LiftingGraph
Time: O(q log n)
Space: O(1)

Problem Overview

Find cycle length in permutation where each step applies the permutation.

Intuition

Find cycle length in permutation where each step applies the permutation. Count cycle containing element 0.

Algorithm

  1. 1Follow permutation from 0 until returning to 0. Count steps.

Common Pitfalls

  • •Permutation forms disjoint cycles. Find the cycle containing index 0.
2509.cs
C#
// Approach: Walk both nodes up to LCA by halving (parent = node/2); count total steps + 1.
// Time: O(q log n) Space: O(1)

public 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;
    }
}
Was this solution helpful?

Related Problems