Problem 16

Problem Statement :Problem16

2¹⁵ = 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¹⁰⁰⁰?

Algorithm:

• The solution use of string multiplication which internally uses string addition.
• For optimization purposes we use 2^39 for the generation of 2^1000 and the remainder 2^25 is taken care in the end.
• In the end  just  sum up the answer that is obtained.

Solution:

import java.util.ArrayList;

public class problem16 {
 // to add two numbers using strings a,b are two numbers
 public static String stringAddition(String a, String b) {
  String sum = "";
  int carry = 0;
  if (a.length() > b.length()) {
   String temp = a;
   a = b;
   b = temp;
  }
  for (int i = 0; i < a.length(); i++) {
   int s = a.charAt(a.length() - 1 - i) + b.charAt(b.length() - 1 - i)
     - 96 + carry;
   if (s > 9) {
    carry = (s - s % 10) / 10;
    s = s % 10;
   } else {
    carry = 0;
   }
   sum = s + sum;
  }

  for (int i = 0; i < b.length() - a.length(); i++) {
   int s = b.charAt(b.length() - a.length() - 1 - i) + carry - 48;

   if (s > 9) {
    carry = (s - s % 10) / 10;
    s = s % 10;
   } else {
    carry = 0;
   }
   sum = s + sum;

  }
  if (carry != 0)
   return carry + sum;
  else
   return sum;
 }

 public static String stringMultiplication(String s1, String s2) {
  String zero = "", num = "";
  ArrayList<String> list = new ArrayList<String>();
  for (int i = s1.length() - 1; i >= 0; i--) {
   int carry = 0;
   int c1 = s1.charAt(i) - '0';
   num = "";
   for (int j = s2.length() - 1; j >= 0; j--) {
    int c2 = s2.charAt(j) - '0';
    int prod = c1 * c2 + carry;
    int add = prod % 10;
    carry = prod / 10;
    num = add + num;
   }
   if (carry != 0)
    num = carry + num;
   list.add(num + zero);
   zero = zero + "0";
  }
  num = "0";
  for (int i = 0; i < list.size(); i++)
   num = stringAddition(num, list.get(i));
  return num;
 }
 
 public static void main(String[] args) {
  String num1="549755813888";//2^39 
  String num2="33554432";//2^25
  String ans="1";
  for(int i=0;i<1000/39;i++)//main power stuff
   ans=stringMultiplication(ans, num1);
  
  ans=stringMultiplication(ans, num2);//remainder stuff
  int sum=0;
  for(int i=0;i<ans.length();i++)
   sum=sum+ans.charAt(i)-'0';
  System.out.println(ans);
  System.out.println(sum);
 }
}