Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 7 of 7

Thread: Efficiency problem

  1. #1
    Junior Member
    Join Date
    Nov 2011
    Posts
    8
    Thanks
    0
    Thanked 1 Time in 1 Post

    Default Efficiency problem

    I have the following problem to solve:

    Find the largest palindromic number made from the product of two N-digit numbers.


    This is my class to find the largest palindromic number:

     
    public class LargestPalindromeNumber {
     
    	private long factorLength, highValue, max = 0, factor1 = 0, factor2 = 0;
     
    	public LargestPalindromeNumber(long n){
     
    		factorLength = n; // number of digits in each factor
    		highValue = (long) (Math.pow(10, factorLength) - 1); // highest value a factor can have
     
    	}
     
     
     
     
    	public long getLargestPalindrome1(){
     
    		for( long i = highValue; i > highValue/10 ; i = i - 1){
     
    			if(i  < factor2) return max;
     
    			for(long j = i ; j > highValue / 10; j = j - 1 ){
     
    				if(i % 11 == 0 || j % 11 == 0){
     
    					if(i*j < max) j = highValue/10;
     
     
    					else{ 
     
    						if(isPalindrome(i * j)){
    						max = i * j;
    						factor1 = i;
    						factor2 = j;
    						j = highValue/10;
     
    					}
    					}
    				}
    			}// end second for loop
     
    		}// end first for loop
     
    		return max;
     
    	}// end getLargestPalindrome()
     
     
    	// Checks whether a number is a palindrome 
    	public boolean isPalindrome(long n){
     
    		long reverse = 0;
    		long value = n;
     
    		while(n > 0){
     
    			reverse = (reverse * 10) + (n % 10);
     
    			n = n / 10;
     
    		}// end while
     
    		return(value == reverse);
     
    	}// end isPalindrome
     
     
    	// Returns the value of factor1
    	public long getFactor1(){
    		return factor1;
    	}
     
     
    	// Returns the value of factor2
    	public long getFactor2(){
    		return factor2;
    	}
     
     
    }// end LargestPalindromeNumber class


    This is my main class:

     
    import tcdIO.*;
     
    public class Main {
     
     
    	public static void main(String[] args) {
     
    		Terminal window;
    		LargestPalindromeNumber bigPal;
    		long ndigit;
     
    		window = new Terminal("Find the Largest Palindromic Number");
     
    		window.println("This program finds the largest palindromic number that is a product of two N-Digit numbers.\n");
    		window.println();
     
    		ndigit = window.readInt("Enter the number of digits in the factors : ");
    		bigPal = new LargestPalindromeNumber(ndigit);
     
     
    		window.println();
    		window.println("The largest palindromic number that is a ");
    		window.println("product of two " + ndigit + " digit numbers is: "); 
    		window.println();
    		window.println( "" + bigPal.getLargestPalindrome1() );
    		window.println();
    		window.println("whose factors are : " + bigPal.getFactor1() + " and " + bigPal.getFactor2() + ".");
     
    	}// end main()
     
    }// end Main class



    Q: Can you suggest ways to improve the efficiency of this code as it takes a long time to get an answer when i enter 9-digit by 9-digit factors, in fact I haven't waited for it to produce an answer yet.

    Note:
    1) The palindromic numbers I am searching for will be divisible by 11.
    2) It works fine up until 8-digit by 8-digit numbers.
    Last edited by Freaky Chris; November 4th, 2011 at 03:05 PM.


  2. #2
    Senile Half-Wit Freaky Chris's Avatar
    Join Date
    Mar 2009
    Location
    Wales, Bangor & England, Warwickshire
    Posts
    820
    My Mood
    Cynical
    Thanks
    7
    Thanked 104 Times in 90 Posts

    Default Re: Efficiency problem

    Have you considered counting insteps of 11?

    Chris
    chris[at]javaprogrammingforums[dot]com

    Prifysgol Bangor University, North Wales

  3. #3
    Junior Member
    Join Date
    Nov 2011
    Posts
    8
    Thanks
    0
    Thanked 1 Time in 1 Post

    Default Re: Efficiency problem

    I have tried that already but its complicated because if the factors are even number digits e.g. 99, I have to decrease i by 11 and j by 1, but if it is an odd number of digits e.g. 999 I have to decrease i by 1 and j by 11. Which sounds simple to implement but it is difficult to insure every possible combination of i * j is checked.

    I'll try again though.

    Edit: Also I let my program run until it found the 9-digit * 9-digit largest palindrome. It took 5/6 minutes and I am fairly sure I cannot compute any palindromes for n-digit factors greater than this as it would result in a number bigger than long can handle. Could you confirm that for me.

    Thanks.
    Last edited by mccolem; November 4th, 2011 at 03:01 PM.

  4. #4
    Senile Half-Wit Freaky Chris's Avatar
    Join Date
    Mar 2009
    Location
    Wales, Bangor & England, Warwickshire
    Posts
    820
    My Mood
    Cynical
    Thanks
    7
    Thanked 104 Times in 90 Posts

    Default Re: Efficiency problem

    I see, I think I may have missed some bits here sorry.

    However, given that you iterate in reverse, starting at max values, that means as soon as you calculate a palindrome, you have the largest possible. So you can stop looping? Or have a missed the point again, and should just crawl into bed lol!


    Edit: Maximum value of long is deffined by Long.MAX_VALUE == 2^63 -1

    Chris
    Last edited by Freaky Chris; November 4th, 2011 at 03:16 PM.
    chris[at]javaprogrammingforums[dot]com

    Prifysgol Bangor University, North Wales

  5. #5
    Junior Member
    Join Date
    Nov 2011
    Posts
    8
    Thanks
    0
    Thanked 1 Time in 1 Post

    Default Re: Efficiency problem

    Quote Originally Posted by Freaky Chris View Post
    I see, I think I may have missed some bits here sorry.

    However, given that you iterate in reverse, starting at max values, that means as soon as you calculate a palindrome, you have the largest possible. So you can stop looping? Or have a missed the point again, and should just crawl into bed lol!


    Edit: Maximum value of long is deffined by Long.MAX_VALUE == 2^63 -1

    Chris

     
    public long getLargestPalindrome1(){
     
    		for( long i = highValue; i > highValue/10 ; i = i - 1){
     
    			if(i  < factor2) return max;
    //Here the method exits if i is smaller than the smallest factor of the current largest palindrome
     
    			for(long j = i ; j > highValue / 10; j = j - 1 ){
     
    				if(i % 11 == 0 || j % 11 == 0){
     
    					if(i*j < max) j = highValue/10; 
    //Here the j loop terminates if i*j is less than the current largest palindrome
     
     
    					else{ 
     
    						if(isPalindrome(i * j)){
    						max = i * j;
    						factor1 = i;
    						factor2 = j;
    						j = highValue/10;
     
    					}
    					}
    				}
    			}// end second for loop
     
    		}// end first for loop
     
    		return max;
     
    	}// end getLargestPalindrome()


    I think I have addressed what you are talking about above. I am still trying to incorporate stepping down by 11 into the method so I'll post when get something.

    Also the first palindrome I get is not necessarily the largest.

    e.g. 2-digit factors, the answer is 9009 whose factors are 99 and 91
    e.g. 3-digit factors, the answer is 906609 whose factors are 993 and 913.

    I would of found a palindrome with i = 999 and j = some integer first but 993*913 was bigger than it.

  6. #6
    Senile Half-Wit Freaky Chris's Avatar
    Join Date
    Mar 2009
    Location
    Wales, Bangor & England, Warwickshire
    Posts
    820
    My Mood
    Cynical
    Thanks
    7
    Thanked 104 Times in 90 Posts

    Default Re: Efficiency problem

    if you loop from highVal to highVal/10 for i and the same for j

    you should always come across the largest possible palindrome first.

    Chris
    chris[at]javaprogrammingforums[dot]com

    Prifysgol Bangor University, North Wales

  7. #7
    Junior Member
    Join Date
    Nov 2011
    Posts
    8
    Thanks
    0
    Thanked 1 Time in 1 Post

    Default Re: Efficiency problem

    If I do that for 3-digit factors, the first palindrome I find is

    995*583 = 580085

    which is smaller than 993*913 = 906609

Similar Threads

  1. Replies: 3
    Last Post: January 5th, 2012, 12:44 AM
  2. variables and efficiency
    By catkinq in forum Java Theory & Questions
    Replies: 3
    Last Post: February 7th, 2010, 05:09 AM