Project Euler: Problem 30 – Digit fifth powers

Problem

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4

As 1 = 1^4 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Solution

This is pretty much easy problem. Here is the solution written in java. And it’s performance pretty cool 🙂

package projecteuler;

/**
 *
 * @author Shaiful Islam Palash
 */
public class Problem30 {
    public static void main(String[] args){
        solution1();
    }

    private static void solution1() {
        long fifthpower[] = new long[10];
        long n = 0; int pow = 5;
        for(int j=0; j<10; j++){
            n += Long.valueOf(CustomMath.pow(9, pow));
            fifthpower[j] = Long.valueOf(CustomMath.pow(j, pow));
        }
        long sumOfFifthPowers = 0;
        for(int i=2; i<n; i++){
            long sum = 0;
            for(char c : String.valueOf(i).toCharArray()){
                sum += fifthpower[Integer.valueOf(String.valueOf(c))];
                if(sum>i) break;
            }
            if(sum == i){
                System.out.println("this is what we look: " + i);
                sumOfFifthPowers += i;
            }
        }
        System.out.println("sum of all the numbers that can be written as the sum of fifth powers of their digits: " + sumOfFifthPowers);
    }
}

package projecteuler;

/**
 *
 * @author Shaiful Islam Palash
 */
public class CustomMath {
    
    public static String pow(long num, long pow){
        String result = "1", numm= String.valueOf(num);
        for (int j = 0; j < pow; j++) {
            result = CustomMath.multiply(result, numm);
        }
        return result;
    }
    
    public static String multiply(String a, String b){
        String result = "0";
        for(long i=0; i<Long.valueOf(b); i++){
            result = CustomMath.sum(result, a);
        }
        return result;
    }
    
    /**
     * Large summation
     * @param aLine
     * @param bLine
     * @return 
     */
    public static String sum(String aLine, String bLine) {
        if (bLine.length() >= aLine.length()) {
            String tmp = aLine;
            aLine = bLine;
            bLine = tmp;
        }

        char[] a = aLine.toCharArray();
        char[] b = bLine.toCharArray();
        StringBuffer sum = new StringBuffer();
        int cA = 0, cB = 0, cC = 0, cS = 0;
        int aLength = a.length - 1;
        int bLength = b.length - 1;

        while (true) {
            if (aLength >= 0) {
                cA = Integer.valueOf(String.valueOf(a[aLength]));
                if (bLength >= 0) {
                    cB = Integer.valueOf(String.valueOf(b[bLength]));
                } else {
                    cB = 0;
                }
                cS = cA + cB + cC;
                if (cS >= 10) {
                    cC = cS / 10;
                    cS = cS % 10;
                } else {
                    cC = 0;
                }
                sum.append(cS);


                aLength -= 1;
                bLength -= 1;
            } else {
                break;
            }
        }
        if (cC > 0) {
            sum.append(cC);
        }
        return sum.reverse().toString();
    }
}
Advertisements

Project Euler: Problem 29 – Distinct powers

Problem

Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

2^2=4, 2^3=8, 2^4=16, 2^5=32
3^2=9, 3^3=27, 3^4=81, 3^5=243
4^2=16, 4^3=64, 4^4=256, 4^5=1024
5^2=25, 5^3=125, 5^4=625, 5^5=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

Solution

I’ve written java programme to solve this problem. Although, I got perfect result but performance of the code is very poor. It took almost 3 minutes to give result. It’s horrible. I need to improve the code. Any one can suggest me about this solution. I would appreciate any kind of suggestion.

I think problem is large summation method. It takes too much time when both numbers are very big.

package projecteuler;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author Shaiful Islam Palash
 */
public class Problem29 {
    public static void main(String[] args){
        solution1();
    }

    private static void solution1() {
        //System.out.println(CustomMath.pow(5, 5));
        int maxA =100, maxB =100;
        List<String> dTerms = new ArrayList<String>();
        for(int a=2; a<=maxA; a++){
            for(int b=2; b<=maxB; b++){
                insertNewDTerms(dTerms, CustomMath.pow(a, b));
            }
        }
        System.out.println("Total distinct terms: " + dTerms.size());
    }
    
    private static List<String> insertNewDTerms(List<String> dTerms, String term){
        boolean isExist = false;
        for(String trm : dTerms){
            if(trm.equalsIgnoreCase(term)){
                isExist = true;
                break;
            }
        }
        if(isExist == false){
            dTerms.add(term);
        }
        return dTerms;
    }
    
    
}


package projecteuler;

/**
 *
 * @author Shaiful Islam Palash
 */
public class CustomMath {
    
    public static String pow(long num, long pow){
        String result = "1", numm= String.valueOf(num);
        for (int j = 0; j < pow; j++) {
            result = CustomMath.multiply(result, numm);
        }
        return result;
    }
    
    public static String multiply(String a, String b){
        String result = "0";
        for(long i=0; i<Long.valueOf(b); i++){
            result = CustomMath.sum(result, a);
        }
        return result;
    }
    
    /**
     * Large summation
     * @param aLine
     * @param bLine
     * @return 
     */
    public static String sum(String aLine, String bLine) {
        if (bLine.length() >= aLine.length()) {
            String tmp = aLine;
            aLine = bLine;
            bLine = tmp;
        }

        char[] a = aLine.toCharArray();
        char[] b = bLine.toCharArray();
        StringBuffer sum = new StringBuffer();
        int cA = 0, cB = 0, cC = 0, cS = 0;
        int aLength = a.length - 1;
        int bLength = b.length - 1;

        while (true) {
            if (aLength >= 0) {
                cA = Integer.valueOf(String.valueOf(a[aLength]));
                if (bLength >= 0) {
                    cB = Integer.valueOf(String.valueOf(b[bLength]));
                } else {
                    cB = 0;
                }
                cS = cA + cB + cC;
                if (cS >= 10) {
                    cC = cS / 10;
                    cS = cS % 10;
                } else {
                    cC = 0;
                }
                sum.append(cS);


                aLength -= 1;
                bLength -= 1;
            } else {
                break;
            }
        }
        if (cC > 0) {
            sum.append(cC);
        }
        return sum.reverse().toString();
    }
}


Programming problem types

There are 16 types of programming problem are appearing in programming contest. They are listed below:

1. Dynamic Programming
2. Greedy
3. Complete Search
4. Flood Fill
5. Shortest Path
6. Recursive Search Techniques
7. Minimum Spanning Tree
8. Knapsack
9. Computational Geometry
10. Network Flow
11. Eulerian Path
12. Two-Dimensional Convex Hull
13. BigNums
14. Heuristic Search
15. Approximate Search
16. Ad Hoc Problems