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

Question

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";
    double answer = Math.round(Math.pow(num, n));
    System.out.println(answer);

    String s = String.valueOf(answer);
    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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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]+");

...

    int counter = not_1.matcher(String.valueOf(answer)).replaceAll("").length();

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.

Answer 5

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), 11ⁿ can be done symbolicly by n such steps.

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