Project Euler #16 - Sum of all digits of 2^1000

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?

    BigInteger big = new BigInteger("2");
big = big.pow(1000);
String num = big.toString();
System.out.println(num);
int result = 0;
for(char i : num.toCharArray()) {
result += Integer.parseInt(String.valueOf(i));
}
System.out.println(result);

• What kind of feedback are you looking for? Is there anything about the code you've posted that you're not satisfied with? Commented Sep 11, 2019 at 14:22
• yes, I feel that there is a better way. instead of converting BigInteger to string and then to charArray and again I return it to int Commented Sep 12, 2019 at 6:48
• Use Character.getNumericalValue(char) instead of Integer.parseInt(String.valueOf(i)). Commented Sep 13, 2019 at 10:38
• @TorbenPutkonen yeah it's more clear. thanks a lot. Commented Sep 15, 2019 at 9:56

This looks good. I assume this results in correct answer.

• What you can use instead of converting to String and back to int is to use divideAndRemainder method with 10 since we need to treat this as a base 10 number.
• This method is available in BigInteger for situations like this.
• We can also directly use BigInteger constants such as TWO and TEN.

Alternative Implementation

BigInteger big = BigInteger.TWO.pow(1000);
String num = big.toString();
System.out.println(num);

int result = 0;
BigInteger[] components;

components = big.divideAndRemainder(BigInteger.TEN);
while (components[0].signum() != 0) {
result += components[1].intValue();
components = components[0].divideAndRemainder(BigInteger.TEN);
}
result += components[1].intValue();
System.out.println(result);

• I've used signum method here to check if result after integer division is zero.
• Note: This seems to be creating lot of objects.

Benchmark with JMH

After the some discussion in comments with @TorbenPutkonen, I agreed with TorbenPutkonen that alternative implementation might be creating more objects. However there is no way to see which implementation performs faster without doing a benchmark.

public class X {

public static void main(String[] a) throws Exception {
org.openjdk.jmh.Main.main(a);
}

@State(Scope.Benchmark)
public static class BenchmarkState {
BigInteger multiple =  BigInteger.TWO.pow(1000);
public BenchmarkState() {
System.out.println(multiple);
}
}

@Benchmark
@Warmup(iterations = 5)
public int withDivide(BenchmarkState x) {
BigInteger[] components;
components = x.multiple.divideAndRemainder(BigInteger.TEN);
int result = 0;
while (components[0].signum() != 0) {
result += components[1].intValue();
components = components[0].divideAndRemainder(BigInteger.TEN);
}
result += components[1].intValue();
return result;
}

@Benchmark
@Warmup(iterations = 5)
public int withChars(BenchmarkState x) {
String num = x.multiple.toString();
int result = 0;
for(char i : num.toCharArray()) {
result += Integer.parseInt(String.valueOf(i));
}
return result;
}

@Benchmark
@Warmup(iterations = 5)
public int withCharsNumerical(BenchmarkState x) {
String num = x.multiple.toString();
int result = 0;
for(char i : num.toCharArray()) {
result += Character.getNumericValue(i);
}
return result;
}

@Benchmark
@Warmup(iterations = 5)
public int withCharAt(BenchmarkState x) {
String num = x.multiple.toString();
int len = num.length();
int result = 0;
for(int i = 0; i < len; i++) {
result += Integer.parseInt(String.valueOf(num.charAt(i)));
}
return result;
}

@Benchmark
@Warmup(iterations = 5)
public int withCharsNumericalCharAt(BenchmarkState x) {
String num = x.multiple.toString();
int len = num.length();
int result = 0;
for(int i = 0; i < len; i++) {
result += Character.getNumericValue(num.charAt(i));
}
return result;
}
}

# Run complete. Total time: 00:21:29

Benchmark                    Mode  Cnt       Score      Error  Units
X.withCharAt                thrpt  200  117285.320 ±  644.505  ops/s
X.withChars                 thrpt  200  116882.706 ±  779.233  ops/s
X.withCharsNumerical        thrpt  200  110849.659 ± 3901.095  ops/s
X.withCharsNumericalCharAt  thrpt  200  121480.705 ± 2040.597  ops/s
X.withDivide                thrpt  200   11306.787 ±   35.711  ops/s

• This concludes that original version is roughly 10x faster than divideAndRemainder
• Original version is also slightly faster than using getNumericValue by itself.
• However we can use charAt and avoid creating a character array too.

Why is using divideAndRemainder slow?

• toString method of BigInteger uses a faster algorithm to create the string representation.
• divideAndRemainder creates lot of BigInteger objects.
• That 's what i looking for... thanks alot Commented Sep 12, 2019 at 10:59
• @OmarAhmed Updated my answer with code. Also if you want to it would be more fun to write the BigInt yourself ;) Commented Sep 12, 2019 at 12:22
• Looking quickly at the code in divideAndRemainder I'd say this approach results in about 2000 or more unnecessary object creations. Despite toString().toCharArray() creating an unnecessary array I would bet that it'd be much more efficient to do it char by char. Commented Sep 13, 2019 at 9:16
• @TorbenPutkonen doesn't Integer.parseInt(String.valueOf(i)) create temporary objects too? This avoids string conversion all together (except for printing). However I'm now curious to run a benchmark and see. 🤔 Commented Sep 13, 2019 at 10:13
• @TorbenPutkonen I've updated the answer with a benchmark. Seems like you are correct. Good catch. :) Commented Sep 14, 2019 at 16:10