programming · project euler

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();
    }
}


Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s