Count number of 1 digits in 11 to the power of N

Question

I came across an interesting problem:

How would you count the number of 1 digits in the representation of 11 to the power of N, 0<N<=1000.

Let d be the number of 1 digits

N=2 11^2 = 121 d=2

N=3 11^3 = 1331 d=2

Worst time complexity expected O(N^2)

The simple approach where you compute the number and count the number of 1 digits my getting the last digit and dividing by 10, does not work very well. 11^1000 is not even representable in any standard data type.

Answer 1

Powers of eleven can be stored as a string and calculated quite quickly that way, without a generalised arbitrary precision math package. All you need is multiply by ten and add.

For example, 111 is 11. To get the next power of 11 (112), you multiply by (10 + 1), which is effectively the number with a zero tacked the end, added to the number: 110 + 11 = 121.

Similarly, 113 can then be calculated as: 1210 + 121 = 1331.

And so on:

11^2   11^3    11^4     11^5      11^6

 110   1210   13310   146410   1610510
 +11   +121   +1331   +14641   +161051
 ---   ----   -----   ------   -------
 121   1331   14641   161051   1771561

So that's how I'd approach, at least initially.

---

By way of example, here's a Python function to raise 11 to the n'th power, using the method described (I am aware that Python has support for arbitrary precision, keep in mind I'm just using it as a demonstration on how to do this an an algorithm, which is how the question was tagged):

def elevenToPowerOf(n):
    # Anything to the zero is 1.

    if n == 0: return "1"

    # Otherwise, n <- n * 10 + n, once for each level of power.

    num = "11"
    while n > 1:
        n = n - 1

        # Make multiply by eleven easy.

        ten = num + "0"
        num = "0" + num

        # Standard primary school algorithm for adding.

        newnum = ""
        carry = 0
        for dgt in range(len(ten)-1,-1,-1):
            res = int(ten[dgt]) + int(num[dgt]) + carry
            carry = res // 10
            res = res % 10
            newnum = str(res) + newnum
        if carry == 1:
            newnum = "1" + newnum

        # Prepare for next multiplication.

        num = newnum

    # There you go, 11^n as a string.

    return num

And, for testing, a little program which works out those values for each power that you provide on the command line:

import sys

for idx in range(1,len(sys.argv)):
    try:
        power = int(sys.argv[idx])
    except (e):
        print("Invalid number [%s]" % (sys.argv[idx]))
        sys.exit(1)

    if power < 0:
        print("Negative powers not allowed [%d]" % (power))
        sys.exit(1)

    number = elevenToPowerOf(power)
    count = 0
    for ch in number:
        if ch == '1':
            count += 1

    print("11^%d is %s, has %d ones" % (power,number,count))

When you run that with:

time python3 prog.py  0 1 2 3 4 5 6 7 8 9 10 11 12 1000

you can see that it's both accurate (checked with bc) and fast (finished in about half a second):

11^0 is 1, has 1 ones
11^1 is 11, has 2 ones
11^2 is 121, has 2 ones
11^3 is 1331, has 2 ones
11^4 is 14641, has 2 ones
11^5 is 161051, has 3 ones
11^6 is 1771561, has 3 ones
11^7 is 19487171, has 3 ones
11^8 is 214358881, has 2 ones
11^9 is 2357947691, has 1 ones
11^10 is 25937424601, has 1 ones
11^11 is 285311670611, has 4 ones
11^12 is 3138428376721, has 2 ones
11^1000 is 2469932918005826334124088385085221477709733385238396234869182951830739390375433175367866116456946191973803561189036523363533798726571008961243792655536655282201820357872673322901148243453211756020067624545609411212063417307681204817377763465511222635167942816318177424600927358163388910854695041070577642045540560963004207926938348086979035423732739933235077042750354729095729602516751896320598857608367865475244863114521391548985943858154775884418927768284663678512441565517194156946312753546771163991252528017732162399536497445066348868438762510366191040118080751580689254476068034620047646422315123643119627205531371694188794408120267120500325775293645416335230014278578281272863450085145349124727476223298887655183167465713337723258182649072572861625150703747030550736347589416285606367521524529665763903537989935510874657420361426804068643262800901916285076966174176854351055183740078763891951775452021781225066361670593917001215032839838911476044840388663443684517735022039957481918726697789827894303408292584258328090724141496484460001, has 105 ones

real    0m0.609s
user    0m0.592s
sys     0m0.012s

That may not necessarily be O(n2) but it should be fast enough for your domain constraints.

---

Of course, given those constraints, you can make it O(1) by using a method I call pre-generation. Simply write a program to generate an array you can plug into your program which contains a suitable function. The following Python program does exactly that, for the powers of eleven from 1 to 100 inclusive:

def mulBy11(num):
    # Same length to ease addition.

    ten = num + '0'
    num = '0' + num

    # Standard primary school algorithm for adding.

    result = ''
    carry = 0
    for idx in range(len(ten)-1, -1, -1):
        digit = int(ten[idx]) + int(num[idx]) + carry
        carry = digit // 10
        digit = digit % 10
        result = str(digit) + result

    if carry == 1:
        result = '1' + result

    return result

num = '1'

print('int oneCountInPowerOf11(int n) {')
print('  static int numOnes[] = {-1', end='')
for power in range(1,101):
    num = mulBy11(num)
    count = sum(1 for ch in num if ch == '1')
    print(',%d' % count, end='')
print('};')
print('  if ((n < 0) || (n > sizeof(numOnes) / sizeof(*numOnes)))')
print('    return -1;')
print('  return numOnes[n];')
print('}')

The code output by this script is:

int oneCountInPowerOf11(int n) {
  static int numOnes[] = {-1,2,2,2,2,3,3,3,2,1,1,4,2,3,1,4,2,1,4,4,1,5,5,1,5,3,6,6,3,6,3,7,5,7,4,4,2,3,4,4,3,8,4,8,5,5,7,7,7,6,6,9,9,7,12,10,8,6,11,7,6,5,5,7,10,2,8,4,6,8,5,9,13,14,8,10,8,7,11,10,9,8,7,13,8,9,6,8,5,8,7,15,12,9,10,10,12,13,7,11,12};
  if ((n < 0) || (n > sizeof(numOnes) / sizeof(*numOnes)))
    return -1;
  return numOnes[n];
}

which should be blindingly fast when plugged into a C program. On my system, the Python code itself (when you up the range to 1..1000) runs in about 0.6 seconds and the C code, when compiled, finds the number of ones in 11¹⁰⁰⁰ in 0.07 seconds.

Answer 2

Here's my concise solution.

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