Bruteforce Algorithm to Compute the Maxmium Powerful Digit Sum u

  • Time:2020-09-09 13:16:32
  • Class:Weblog
  • Read:28

A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?

Maxmium Powerful Digit Sum using Java’s BigInteger

Given a and b are in short range of [0 to 99]. There bruteforce algorithm should be more than enough to solve the problem. We need to check total 100*100 different combinations of a to the power b.

In order to hold such large number, we can use array, or in Java, we can simply use the java.math.BigInteger. See below Java’s trivial implementation using the BigInteger. The result (BigInteger) is converted to String type, then the digits are sum, then updating the maximum.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package com.helloacm;
 
import lombok.var;
import java.math.BigInteger;
 
public class Main {
    public static void main(String[] args) {
        int ans = 0;
        for (var a = 2; a < 100; ++ a) {
            for (var b = 2; b < 100; ++ b) {
                var c = BigInteger.valueOf(a).pow(b);
                var v = c.toString();
                var sum = 0;
                for (var x: v.toCharArray()) {
                    sum += x - 48;
                    ans = Math.max(sum, ans);
                }
            }
        }
        System.out.println(ans);
    }
}
package com.helloacm;

import lombok.var;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        int ans = 0;
        for (var a = 2; a < 100; ++ a) {
            for (var b = 2; b < 100; ++ b) {
                var c = BigInteger.valueOf(a).pow(b);
                var v = c.toString();
                var sum = 0;
                for (var x: v.toCharArray()) {
                    sum += x - 48;
                    ans = Math.max(sum, ans);
                }
            }
        }
        System.out.println(ans);
    }
}

The answer is 972.

–EOF (The Ultimate Computing & Technology Blog) —

Recommend:
5 Trust Indicators And How To Use Them To Grow Your Blog
How to Merge k Sorted Lists using Recursive Divide and Conquer A
The String ZigZag Conversion Algorithms
How Experts Make Your Website Successful?
Replace Elements with Greatest Element on Right Side using C++ s
Compute the Deepest Leaves Sum of a Binary Tree using BFS or DFS
Microbit Programming: Snake Game with Growing Body and Greedy St
How to Make a Simple Snake Game in Javascript?
Integration Tests Using PHPUnit to Ensure Your Website is Workin
Find Out the Longest Arithmetic Sequence in Array Using Dynamic
Share:Facebook Twitter
Comment list
Comment add