Wednesday, February 1, 2012

Problem 20


Problem Statement :Problem21



n! means n × (n − 1) × ... × 3 × 2 × 1
For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.
Find the sum of the digits in the number 100!


Approach:
  • For solving this we use the same multiplication of strings method as used earlier
  • Then add the sum of digits 

Solution:
    import java.util.ArrayList;
    
    public class problem20 {
     // 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 sum = "1";
      for (int i = 2; i <= 100; i++) {
       sum = stringMultiplication(sum, i + "");
      }
      int num = 0;
      for (int i = 0; i < sum.length(); i++)
       num += (sum.charAt(i) - '0');
      System.out.println(num);
     }
    }
    


No comments:

Post a Comment