public class FibonacciNums
{
    /// <summary>
    /// Time Complexity: O(n) - The loop runs 'n' times to calculate the value.
    /// Space Complexity: O(1) - Only a constant amount of extra space (a few BigInteger variables) is used.
    /// </summary>
    public BigInteger GetNthFibonacci(int n)
    {
        if (n < 0) throw new ArgumentOutOfRangeException(nameof(GetNthFibonacci), "Index must be non-negative.");
        if (n == 0) return 0;
        if (n == 1) return 1;

        BigInteger a = 0;
        BigInteger b = 1;

        for (int i = 2; i <= n; i++)
        {
            BigInteger temp = a + b;
            a = b;
            b = temp;
        }

        return b;
    }
    
    /// <summary>
    /// Time Complexity: O(log(max)) - Fibonacci numbers grow exponentially, so the number of iterations 
    /// to reach 'max' is logarithmic relative to the value of 'max'.
    /// Space Complexity: O(count) - Where 'count' is the number of Fibonacci numbers found within the range, stored in the result list.
    /// </summary>
    public List<BigInteger> GetFibonacciInRange(BigInteger min, BigInteger max)
    {
        var result = new List<BigInteger>();
        BigInteger a = 0;
        BigInteger b = 1;
        
        // we generate them and keep them if withing range (less expensive than checking each num separately)
        // We continue as long as 'a' (the current number) hasn't passed the max
        while (a <= max)
        {
            // Only capture it if it's within the lower bound
            if (a >= min)
            {
                result.Add(a);
            }

            BigInteger next = a + b;
            a = b;
            b = next;
        }

        return result;
    }

    /// <summary>
    /// Time Complexity: O(n) - We iterate 'n' times to fill the array.
    /// Space Complexity: O(n) - An array of size 'n' is allocated to store the results.
    /// </summary>
    public long[] FirstXNumbers(int n)
    {
        if (n <= 0) return [];
        if (n == 1) return [0];

        var result = new long[n];
        result[0] = 0;
        result[1] = 1;

        for (var i = 2; i < n; i++)
        {
            result[i] = result[i - 1] + result[i - 2];
        }

        return result;
    }
    
    /// <summary>
    /// Time Complexity: O(1) - Uses a constant number of mathematical operations and a square root calculation.
    /// Space Complexity: O(1) - No additional space proportional to the input is used.
    /// </summary>
    public bool IsFibonacci(int num)
    {
        if (num < 0) return false;
            
        return IsPerfectSquare(5L * num * num + 4) || IsPerfectSquare(5L * num * num - 4);
    }

    /// <summary>
    /// Time Complexity: O(1) - Uses a constant number of mathematical operations and a square root calculation.
    /// Space Complexity: O(1) - No additional space proportional to the input is used.
    /// </summary>
    private static bool IsPerfectSquare(long x)
    {
        if (x < 0) return false;
        var s = (long)Math.Sqrt(x);
        return s * s == x;
    }
    
}