Counting number of 1 digits in the value of $11^n$

I am trying to improve the efficiency of my code,

The Question is:

Given a value n, where n is in the range [0 .. 500], return the number of digits equal to 1 in the decimal representation of the number $$\11^n\$$.

Naturally when dealing with a larger power (where n is a large number), this reduces the efficiency drastically.

I managed to produce a quick but inefficient rough solution, that seems to work, but what could I do to improve the code and its efficiency?

import java.util.ArrayList;

public class Solution {

private static int num = 11;

public static int solution(int n) {

int counter = 0;
String compare = "1";

String[] parts = s.split("");

for (int i=0; i<parts.length; i++){
if (parts[i].equals(compare)){
counter++;
}
}
System.out.println(counter);
return counter;
}

public static void main(String[] args) {

solution(8);
solution(3);

}
}


Any help in improving my understanding of the techniques of writing more efficient code would be much appreciated as well as improvements to the code example above.

• Welcome to Code Review! Is this from a programming challenge or some kind of homework? If so, please include a (or at least link to) the description of the task. Dec 2 '19 at 16:15
• Hi @AlexV, its from a programming challenge i was completing, but did not think my code was up to scratch, i will add the question in an edit, thanks in advance Dec 2 '19 at 16:18

You should put your programming skills aside for a bit and think. Think mathematically, what it actually means.

$$11^n = (10+1)^n$$

Lets say a=10, b=1 => $$\(a+b)^n\$$, this can be expanded using pascal triangle:

   1
1 1
1 2 1
1 3 3 1
...


I suppose everybody knows how this continues...

It then goes like this:

$$(a+b)^n = {n \choose 0} a^n b^0 + {n \choose 1} a^{n-1} b^1 + \dots + {n \choose n} a^0 b^n$$

You can notice that since b=1 we can erase all those terms $$\b^x\$$

And we are left with $$(a+b)^n = {n \choose 0} a^n + {n \choose 1} a^{n-1} + \dots + {n \choose n} a^0$$

Since a=10, we know $$\a^n\$$ is basically a 1 followed by n zeroes.

Simple add and carry of the coefficients should now show you when a digit is 1 and when it is anything else.

• +1 I'm writing an answer, but probably this is the best method. Dec 3 '19 at 8:06
• Curiosity got the better of me. ${500 \choose 9} = 5006325637513057000$, which is 63 bits (the limit of long). The largest coefficient, ${500 \choose 250}$, takes 496 bits, so you're still well into the range of needing extended precision integers. $11^{500}$ requires 1730 bits, so you have reduced the range of extended precision integers required by 70%, which is a win, but doesn't win enough to avoid needing BigInteger or similar to solve the problem. Dec 4 '19 at 22:04
• To be fair, the largest exponent, where ${n \choose r}$ is still within a 64 bit long for all $r$ would be $n = 66$, which is a huge improvement over the $n \le 15$ limit for the 53-bit mantissa double implementation in the original post. My testing shows that even intermediate accumulations do not exceed 63 bits for $n \le 66$. Dec 4 '19 at 22:30
• Note: Without heroic efforts, ${n \choose r}$'s internal calculations will overflow 63 bits for some $r$, when $n \ge 62$, even though the return value can be properly represented by a long, placing a slightly lower limit on this approach: $n \le 61$, instead of $n \le 66$, if not using BigInteger or similar. Dec 4 '19 at 22:49
• @AJNeufeld You have a sharp eye, sir! I have actually realized that later on. But I wanted to think about it a bit deeper before I make an edit to mention that. But I haven't yet had the time for that. And honestly I was really curious if anyone would notice :) Dec 6 '19 at 7:51

The implementation is wrong, and will return incorrect results once n exceeds 15.

A double stores values using a 53 bit mantissa, allowing accurate representation of values with approximately 16 digits of precision. When $$\n \gt 16\$$, then $$\11^n \gt 10^{16}\$$, and the double value runs out of precision, and cannot represent the value precisely. This inaccuracy implies that you cannot count the number of 1 digits in the result with any hope of returning the correct value.

It should not take long to convince yourself that $$\11^n\$$ will always end in a 1 digit. Now, consider, $$\11^{16} = 45949729863572161\$$, and compare with:

jshell> String.valueOf(Math.round(Math.pow(11, 16)))
\$20 ==> "45949729863572160"


To accurately count the number of 1 digits, you need to use extended precision integers (ie, BigInteger) or an algorithm which determines the desired value in a different fashion.

Splitting a string with a regular expression is probably the least efficient way of counting 1 digits. On top of the regular expression penalty, the JVM needs to allocate a String[], as well as one String per character in the string. A much more efficient way of counting 1 digits is to extract the digits one at a time as characters (not strings):

int counter = 0;
for(int i = 0; i < s.length; i++)
if (s.charAt(i) == '1')
counter++;


Like the other answers before mine, the problem is about big values of exp n. If you took pen and paper and try for example to multiplicate 1331 ($$\11^3\$$) and 11 to obtain number 14641 ($$\11^4\$$) you do in this way:

 1331 x
11
-------
1331 +
1331
-------
14641


So basically if you have $$\11^n\$$ and you want to calculate $$\11^{n+1}\$$ it can be calculated with the sum of the $$\11^n\$$ and $$\11^n * 10\$$. To avoid problem due to the dimensions of numbers you can write the the numbers with strings. In the case of number 1331 we can use sum the strings 01331 and 13310 and calculate string 14641.

I defined a class called PowerOfEleven and a main method containing the tests below:

public class PowerOfEleven {
private static String ELEVEN = "11";
private static String ZERO = "0";
private static String ONE = "1";

public static void main(String[] args) {
assertEquals(calculatePower(0), "1");
assertEquals(calculatePower(1), "11");
assertEquals(calculatePower(2), "121");
assertEquals(calculatePower(3), "1331");
assertEquals(calculatePower(4), "14641");
assertEquals(calculatePower(5), "161051");
assertEquals(calculatePower(6), "1771561");
}
}


The method calculatePower calculates for every n the number $$\11^n\$$ using the sum of strings like when you use pen and paper:

public static String calculatePower(int n) {
if (n == 0) { return ONE; }
String number = ELEVEN ;
for (int i = 1; i < n; ++i) {
String first = ZERO  + number;
String second = number + ZERO;
number = sum(first, second);
}
return number;
}


I'm adding the strings putting one zero before the first string and another zero after the second string, so for example for number 1331 you obtain strings 01331 and 13310. I defined a method for the sum of the strings like below:

private static String sum(String s1, String s2) {
final int n = s1.length();
char[] arr1 = s1.toCharArray();
char[] arr2 = s2.toCharArray();

StringBuilder result = new StringBuilder();
int remainder = 0;
for (int i = n - 1; i >= 0; --i) {
int firstDigit = Character.getNumericValue(arr1[i]);
int secondDigit = Character.getNumericValue(arr2[i]);
int value = firstDigit + secondDigit + remainder;
remainder = 0;
if (value >= 10) {
value = value - 10;
remainder = 1;
}
result.append(Character.forDigit(value, 10));
}
if (remainder > 0) {
result.append(remainder);
}

return result.reverse().toString();
}


The method uses a StringBuilder object to store the result : when you sum the digits of the two strings starting from the end you obtain a new digit and a remainder that can be 0 or 1. The new digit obtained from the sum is appended at the of the StringBuilder, so you have to reverse the StringBuilder result to obtain the real value.

Note : @slepic idea of using Pascal triangle if implemented simplifies my idea of sum of strings and surely improves performance.

• 11^(n+1) = 10 * 11^n + 11^n is a very nice identity. I wonder why your answer is on the bottom. But i suppose it's because your answer came the last... Big thumbs up for thinking about the math behind the problem first! Dec 3 '19 at 16:26

This looks like its complexity will scale linearly with n, so I'm surprised it's a performance bottleneck. Consider just leaving it as-is.

Discussion about counting the digits of an int suggests that the overhead of String allocation may be worth the bother of avoiding.
(I'm a little surprised; I wonder if we'd see the same difference in C or not.)
On the other hand, your situation is a little more complicated than theirs; you may not see the same efficiency if you take the (larger) pains of implementing the int-only solution.

Within the space of string-based solutions, you may be better off without an explicit loop. A compiled regex would look good on paper, but I bet its heavy under the hood.

private static Pattern not_1 = Pattern.compile("[^1]+");

...



If it's clear enough to you and your peers what that says, then I'd advocate using it because it's clear and concise. If you've specifically identified this function as a performance bottleneck though, then you'll need to write up a couple implementations and do some bench-marking to know which one's best.

Your raw solution should use BigInteger:

public static int solution(int n) {
BigInteger elevenUpN = BigInteger.valueOf(11).pow(n);

String repr = elevenUpN.toString();
int ones = (int) repr.codePoints().filter(cp -> cp == '1').count();
System.out.printf("11^%d = %s with %d ones%n", n, repr, ones);
return ones;
}


As multiplication by 11 is a shift and addition (*1 + *10), 11n can be done symbolicly by n such steps.

Use an array of n+1 digit values, the least significant at index 0 (hence reversed).

• From How do I write a good answer?: "Every answer must make at least one insightful observation about the code in the question. Answers that merely provide an alternate solution with no explanation or justification do not constitute valid Code Review answers and may be deleted." This is not a valid answer; it is just an alternate (working) solution. Do not solve programming challenges for other users; do review their code, point out bugs, inefficiencies, style issues, etc. Dec 3 '19 at 21:17
• "Use an array of n+1 digit values": This is incorrect. $11^{500}$ has 521 digits in the result, not a mere 1 more than 500. Dec 3 '19 at 21:25