11的1位数数到N的幂

Question

我遇到了一个有趣的问题：

如何计算11的表示中1位数到N，0<N<=1000的幂。

设d为1位数

N=2 11^2 =121个d=2 N=3 11^3 = 1331 d=2

最坏的时间复杂度期望O(N^2)

简单的方法，你计算的数字和数的数字，我得到的最后一个数字，除以10，不是很好的工作。11^1000甚至在任何标准数据类型中都不能表示。

Answer 1

这是我的简明解决方案。

def count1s(N):
    # When 11^(N-1) = result, 11^(N) = (10+1) * result = 10*result + result
    result = 1
    for i in range(N):
        result += 10*result

    # Now count 1's
    count = 0
    for ch in str(result):
        if ch == '1':
            count += 1
    return count

Answer 2

En c#：

        private static void Main(string[] args)
    {
        var res = Elevento(1000);
        var countOf1 = res.Select(x => int.Parse(x.ToString())).Count(s => s == 1);
        Console.WriteLine(countOf1);
    }

    private static string Elevento(int n)
    {
        if (n == 0) return "1";
        //Otherwise, n <- n * 10 + n, once for each level of power.
        var num = "11";
        while (n > 1)
        {
            n--;
            // Make multiply by eleven easy.
            var ten = num + "0";
            num = "0" + num;
            //Standard primary school algorithm for adding.
            var newnum = "";
            var carry = 0;
            foreach (var dgt in Enumerable.Range(0, ten.Length).Reverse())
            {
                var res = int.Parse(ten[dgt].ToString()) + int.Parse(num[dgt].ToString()) + carry;
                carry = res/10;
                res = res%10;
                newnum = res + newnum;
            }

            if (carry == 1)
                newnum = "1" + newnum;
            // Prepare for next multiplication.
            num = newnum;
        }
        //There you go, 11^n as a string.
        return num;
    }