< Summary

Information
Class: LeetCode.Algorithms.CountGoodNumbers.CountGoodNumbersFastExponentiation
Assembly: LeetCode
File(s): D:\a\LeetCode-CS\LeetCode-CS\source\LeetCode\Algorithms\CountGoodNumbers\CountGoodNumbersFastExponentiation.cs
Line coverage
100%
Covered lines: 18
Uncovered lines: 0
Coverable lines: 18
Total lines: 51
Line coverage: 100%
Branch coverage
100%
Covered branches: 4
Total branches: 4
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
CountGoodNumbers(...)100%11100%
ModPow(...)100%44100%

File(s)

D:\a\LeetCode-CS\LeetCode-CS\source\LeetCode\Algorithms\CountGoodNumbers\CountGoodNumbersFastExponentiation.cs

#LineLine coverage
 1// --------------------------------------------------------------------------------
 2// Copyright (C) 2025 Eugene Eremeev (also known as Yevhenii Yeriemeieiv).
 3// All Rights Reserved.
 4// --------------------------------------------------------------------------------
 5// This software is the confidential and proprietary information of Eugene Eremeev
 6// (also known as Yevhenii Yeriemeieiv) ("Confidential Information"). You shall not
 7// disclose such Confidential Information and shall use it only in accordance with
 8// the terms of the license agreement you entered into with Eugene Eremeev (also
 9// known as Yevhenii Yeriemeieiv).
 10// --------------------------------------------------------------------------------
 11
 12namespace LeetCode.Algorithms.CountGoodNumbers;
 13
 14/// <inheritdoc />
 15public class CountGoodNumbersFastExponentiation : ICountGoodNumbers
 16{
 17    private const int Mod = 1_000_000_007;
 18
 19    /// <summary>
 20    ///     Time complexity - O(log n)
 21    ///     Space complexity - O(1)
 22    /// </summary>
 23    /// <param name="n"></param>
 24    /// <returns></returns>
 25    public int CountGoodNumbers(long n)
 926    {
 927        var evenPositions = n / 2;
 928        var oddPositions = n - evenPositions;
 29
 930        return (int)(ModPow(5, oddPositions) * ModPow(4, evenPositions) % Mod);
 931    }
 32
 33    private static long ModPow(long value, long exponent)
 1834    {
 1835        long result = 1;
 36
 5737        while (exponent > 0)
 3938        {
 3939            if (exponent % 2 == 1)
 2540            {
 2541                result = result * value % Mod;
 2542            }
 43
 3944            value = value * value % Mod;
 45
 3946            exponent /= 2;
 3947        }
 48
 1849        return result;
 1850    }
 51}