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

Question

I ran into an interesting problem: how would you calculate the number 1 digits in representation 11 for power N, 0<N<=1000 .

Let d be a 1-digit number

N = 2 11 ^ 2 = 121 d = 2

N = 3 11 ^ 3 = 1331 d = 2

Worst time complexity expected O (N ^ 2)

A simple approach, in which you calculate the number and count the number of 1 digits, getting the last digit and dividing by 10, does not work very well. 11 ^ 1000 cannot even be reproduced in any standard data type.

Any ideas?

Answer 1

The forces of eleven can be stored as a string and calculated quite quickly this way, without a generalized mathematical package of arbitrary accuracy. All you need to do is multiply by ten and add.

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

Similarly, 11 3 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, how would I get closer, at least initially.

---

As an example, here is a Python function to raise 11 to the nth degree using the method described (I know that Python supports arbitrary precision, remember that I just use it as a demonstration of how to do this, an algorithm in which the question was marked):

 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 small program that provides these 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 this with:

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

you can see that it is both accurate (marked 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 , has 105 ones real 0m0.609s user 0m0.592s sys 0m0.012s 

This may not necessarily be O(n 2 ) , but it should be fast enough to restrict your domain.

---

Of course, given these limitations, you can make it O(1) using the method that I call to pre-generate. Just write a program to create an array that you can connect to your program, which contains a suitable function. The following Python program does just that, for eleven powers 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 output of this script:

 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 dazzling when connected to program C. On my system, the Python code itself (when it reaches the range up to 1..1000 ) starts in about 0.6 seconds, and the C code, when compiled, finds a number from 11 ¹⁰⁰⁰ in 0.07 seconds.

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; } 

Answer 3

Here is my brief 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