palindrome

[vince1981]

I'm working on an assignment to find the largest palindrome that is the product of 2 three-digit numbers. So the factors could be anything from 100 to 999 and the products to check would be between 10,000 and 99,801.

To make the program a little more versatile, I'd like to get from the user either the bounds on a range (i.e., high number and low number) or the number of digits in the high number and low number. The code below would get the number of digits for the bounds of the range, but I could just as easily edit the user prompt to ask for a low number and high number:

cout>>"How many digits are in the lowest number of your range?">>endl;
cin<<lowdigit;
cout>>"How many digits are in the highest number of your range?">>endl;
cin<<highdigit;

For my particular problem, the user would enter 3 and 3 or 100 and 999, depending on which approach I take.

From there, I was thinking about using some kind of array to check for palindromes, but I'm having trouble even getting the logic of it in my head. Can anyone point me in the right direction? I'm not necessarily looking for code, just some ideas. If possible, I'd like to avoid brute force as much as possible.

Thanks,

Vince

[zwA4jE8b]

you can read the number into a char array then use indexes to compare.

char _input[3];
std::cin.getline(_input, 3, '\n');

that may help you with the first part.

[kev82]

I'm not sure you can avoid brute force, other than generating each palindrome (starting with largest) and then checking if it has a factor between 100 and 999 I can't see what else to do.

[buffbill]

[s]It really doesn`t matter what the user enters (how many digits)....all you need to do is is compare the first and last digits of the string. Iff they are equal go to the second and second last digits and repeat the comparison. You could use pointers to the first and last digit and then increment and reverse increment them until you have covered half the string for each or found an inequality. The length() function could provide the length of the string and the basis of the loop condition statement..[s]
Edit:The above is wrong ........I miss understood the question. The number probably has to be converted into six individual digits and be held in a type of container where the first and last digits can be compared for equality and then the second and second last and so on. Converting to a string is feasible using sprintf() but appears not to offer an advantage.

[vince1981]

I'm not sure you can avoid brute force, other than generating each palindrome (starting with largest) and then checking if it has a factor between 100 and 999 I can't see what else to do.

So you think finding the palindromes first would be the more efficient way? If that's the case, how about the logic (and pseudocode) below:

#include<iostream>
using namespace std;

bool ispalindrome (int pal)
{
/*Determines if pal is a palindrome. If yes, return true. If no, return false.

I'm thinking of writing the first half of the number to one string/array and the other half, in reverse, to a second array. 
We can discard the middle digit if there are an odd number of digits. If the corresponding numbers in 
the two arrays are equal, we have a palindrome. Would it be easier to simply write the whole number 
to a string/array and compare moving inward from the beginning and end of the string?*/
}

bool factorsinrange (int a)
{
/*Find the factor pairs of working and determine if any pair lies within the range of low^2 and 
high^2. If yes, output the two factors and return true. If no, return false.*/
}

int main ()
{
int low, high, working;
bool highestpalindrome=false;

//Gets the lowest number in the range
cout<<"Enter the lowest number in your range."<<endl;
cin>>low;

//Gets the highest number in the range
cout<<"Enter the highest number in the range"<<endl;
cin>>high;

working=high*high;

while (working>=low*low && highestpalindrome==false)
{
   if (ispalindrome(working))
   {

     if (factorsinrange(working))
     {
     cout<<"The largest palindrome that is the product of two numbers in the range you entered is: ";
     cout<<working<<"."<<endl;
     highestpalindrome=true;
     }
   }
   else working--;
}

return(0);
}

[kev82]

Your code works, but it is not as efficient as generating the palindromes. You will be looping over numbers that are neither a palindrome nor have the correct factors - non palindromic primes for example. You will be calling is_palindrome for each of them.

My solution is more like

Palindrome p(high*high)
while(!p.hasFactor()) --p;

Where --p moves generates the first plaindrome lower than p.

[shacktar]

Another problem is given a palindrome, finding if it is a product of two three digit numbers. Do you loop through all the numbers from 100 to 999 and see if the number divides it evenly (into a three-digit number)? Is there a better way to do this?

The choice is either to a) enumerate through all the products (a lot of them, naturally starting from the largest) and do a (relatively cheap) is_palindrome call OR b) to cleverly enumerate through all the palindromes (not as many of them, naturally starting at the largest) and do a (potentially very expensive) is_product_of_two_three_digit_numbers call.

My gut tells me that enumerating through the palindromes is the faster method. Either way, if I were you, I would concentrate on getting a brute force implementation working first. I would start on enumerating through all the products and checking if the product is a palindrome (this could be implemented rather quickly). I would then start working on kev82's method of generating palindromes.

[kev82]

Let p be a list of primes up to 1000, this can be hardcoded or use a sieve.

//Assumes x>=1000
bool has3DigitFactor(x) {
  int f=1;
  int i=0;
  while(f*p[i] < 1000) {
    while(x%p[i] == 0) {
      f *= p[i];
      x/=p[i];
      if(f >= 100 && f < 1000) return true;
      if(x >= 100 && x < 1000) return true;
    }
    ++i
  }
  return false;
}

I'm actually a little curious to find out if that is faster/slower than looping from 100 to 999.

[shacktar]

It must be faster.

There are 900 numbers between 100 and 999, inclusively.

The worst-case performance of "has3DigitFactor" is proportional to the number of prime factors "x" has. No number between 10,000 and 998,001 has anything even remotely close to 900 prime factors.

[kev82]

It doesn't work anyway. I realised this morning that the number of factors with n distinct prime factors is 2^n, this does not consider all of them, and sometimes misses the 3 digit ones. 2*2*3*5*17*59 for example.

[vince1981]

So I'm trying the brute force method, and trying to determine the number of digits in a given number so I know how big to make my array. I guess I could just do an array with like 50 elements, but that'll eat unnecessary memory. Once the if evaluates to true, it should set "numdig" to equal "count" (which initializes to 1)



Here's what I have so far:

int numdig=0, lowcheck=0, highcheck=10, count1=1;
int working, pal;

cout<<"Enter a positive number."<<endl;
cin>>pal;
working=pal;

//determines how many digits are in a number    
    while (numdig=0)
    {
        if (working>=lowcheck&&working<highcheck)
        {
            numdig=count1;
        }
        else
        {
            lowcheck=highcheck;
            highcheck=highcheck*10;
            count1++;
        }
    }
    cout<<pal<<" has "<<numdig<<" digits."<<endl;

No matter what number I enter, my output is 0. What am I missing here?

[quirkyusername]

you can get iterators to the beginning and the end of a string with string::begin() and string::rend(), if you step forward from begin and back from rend and find a difference between any pair you'll know it's not a palindrome

[ne555]

To "reverse" a number considerer it as an array of digits. (actually as an stack)

n%10 -> top()

n/10 -> pop()

n *= 10
n += digit -> push(digit)

[vince1981]

Got the number of digits portion of the program working. Now I'm having trouble with arrays. This is the first time I've worked with them. Can someone tell me if what I'm doing here can work:

#include<iostream>
using namespace std;

int main()
{
    int counter=0;
    int working=0;
    
    cout<<"How many digits does your number have?"<<endl;
    cin>>counter;
    cout<<"What is your number?"<<endl;
    cin>>working;

    //creates an array with counter elements and writes the digits of working
    //into the array
    int palcheck[counter];    
    for (;counter>=1; counter--)
    {
        palcheck[counter-1]=working%10;
        working=(working-(working%10))/10;
    }

    int numdig=counter;

    //displays the digits in the array
    cout<<"The digits of your number are:"<<endl;    
    do
    {
        cout<<palcheck[counter]<<"   "<<endl;
        counter++;
    }
    while (counter<numdig);

system("pause");
return(0);
}

Everything compiles ok, but my output looks like this:

How many digits does your number have?
4
What is your number?
1234
The digits of your number are:
1
Press any key to continue . . .

It seems to be skipping all but the first iteration of the do-while loop. If I remove the loop and use cout<<palcheck[0]<<palcheck[1]<<palcheck[2]<<palcheck[3]<<endl;

It outputs the correct numbers, so I know everything is getting into the array correctly.

What am I doing wrong?

[ne555]

int palcheck[counter]; ISO C++ forbids variable length array.

    int numdig=counter;
    do
    {
        //stuff
        counter++;
    }
    while (counter<numdig);

¿Do you see it?

working=(working-(working%10))/10; You forgot to calculate the factorial of 150

[shacktar]

Your program is only showing the first digit because at this point:

int numdig=counter;

counter == 0 (so numdig is zero). Therefore, it only does the last loop once (counter turns to 1 so it exits). Since you already asked how many digits there are in the number, you can save that after the user inputs it.

------

Also, if you're thinking of going the generating palindromes/figuring out if the palindrome is a product of two three digit numbers route, I have thought of a method to tackle the "is a product of two three digit numbers" problem.

You could first get the prime factors of the number (using a modification of kev82's approach), and then look at combinations of those factors. You would be splitting the prime factors into two sets and checking if both sets each multiply to a three digit number.

e.g.

Given this number: 2*2*3*5*17*59 = 60180, it is a product of two three digit numbers because 2*59=118 and 2*3*5*17=510 and therefore 60180=118*510

To find this we first enumerate all the combinations involving one prime factor. That is, we look at each prime factor, and if it is a three digit number, we multiply the other factors and see if that is a three digit number. Since none of the prime factors are three digit numbers, we are done this step.

Next, we enumerate over all the combinations involving two prime factors. If they multiply to be a three digit number, then we multiply the remaining factors to see if they multiply to a three digit number.

2 * 2 = 4 ... next
2 * 3 = 6 ... next
2 * 5 = 10 ... next
2 * 17 = 34 ... next
2 * 59 = 118. This is a candidate. The other factors are 2,3,5, and 17 and they multiply to 510 which has three digits, so we have found two three digit factors!

For numbers which have 6 prime factors like this one, you would only need to enumerate the combinations involving 1, 2, and 3 factors (since looking at all combinations involving 2 factors is the same as looking at all the combinations involving 4 factors, and similarly looking at all combinations involving 5 factors is the same as looking at all the combinations involving 1 factor, etc.) This is a maximum of only 41 combinations to enumerate. For a number with 7 prime factors, this would be 63 combinations. For a number with 8 prime factors, this would be 162 combinations. For a number with 9 prime factors, this would be 255 combinations, and for a number with 10 prime factors, this would be 637 combinations. Hopefully, no number between 100*100 and 999*999 would have more than 10 prime factors because the combinations to enumerate would go over the worst case of 900 possible three digit numbers to check as possible factors.

This is beginning to sound like a damned if you do, damned if you don't type problem...Good luck!

[vince1981]

Here's my final code to determine if a number is a palindrome:

#include<iostream>
using namespace std;

int main()
{

    int pal;
    int working=0;
    int numdig=0;
    int counter;

    cout<<"Enter a positive number."<<endl;
    cin>>pal;
    working=pal;

    //determines how many digits are in a number (verified that this works)
    while (working>0)
    {
       working=(working-(working%10))/10;
       numdig++;
    }
    
    cout<<pal<<" has "<<numdig<<" digits."<<endl;

    //creates an array with counter elements and writes the digits of working
    //into the array (verified that this works)
    counter=numdig;
    working=pal;
    int palcheck[counter];    
    for (;counter>=1; counter--)
    {
        palcheck[counter-1]=working%10;
        working=(working-(working%10))/10;
    }

    //displays the digits in the array (verified that this works)
    cout<<"The digits of your number are:"<<endl;    
    do
    {
        cout<<palcheck[counter]<<"   ";
        counter+=1;
    }
    while (counter<numdig);
    cout<<endl;

    
    //compares the corresponding elements of the array to determine if they are
    //equal
    int counter2=numdig-1;
    counter=0;
    
    if (palcheck[counter]<palcheck[counter2])
    {
        counter++;
        counter2--;
    }
    
    else if (palcheck[counter]==palcheck[counter2])
    {
        cout<<pal<<" is a palindrome."<<endl;
    }

    //return (true);
        
    else cout<<pal<<" is not a palindrome."<<endl;
    
    system("pause");
    return(0);
}

Thanks for everyone's help so far. As I proceed, any comments on the above code?

Also, if I use the above code in a function that I call for each number I want to check, will the array I've created go away after each iteration of the function, or do I need to do something to free up that memory? Or will redeclaring the array reset things when the function runs again?

[vince1981]

I'm getting extremely close. I'm able to identify all the palindromes, but something is up with my code when I try to find the three-digit factors (see code below).

For starters, *cough*IGoogledtheanswer*cough*, I know that the program is skipping over the palindrome I'm looking for (it is identifying it as a palindrome, but is not getting the three digit factors and stopping the program.

Secondly, the program enters an infinite loop when it gets to 90909, which incidentally fits the bill except that it's not the largest. So without further ado, here's the code in question:

//3. factor must be >= low or any palindromes will be outside
//the specified range
if (factor1>=low)
{
    //4. factor divides evenly into working and is within
    //the specified range
    if (working%factor1==0)
    {
        //temp; we've found a viable factor
        cout<<factor1<<endl;
        system("pause");
        
        //initialize factor2 to determine if it's within
        //the specified range
        factor2=working/factor1;
        
        //5. factor1 is within specified range; if factor2
        //is as well, working is the palindrome the program
        //is trying to find
        if (factor2>=low)
        {
            cout<<"The largest palindrome that is the ";
            cout<<"product of two numbers found in the ";
            cout<<"specified range is "<<working<<endl;
            cout<<"It is the product of "<<factor2<<" and ";
            cout<<factor1<<"."<<endl;
            
            progcomplete=true;
        }
        
        //5. factor1 doesn't have a partner; check next factor
        else
        {
            factor1--;
        }
    }
    
    //4. factor is not a factor of working
    else
    {
        working--;
    }
}
    
//3. no two numbers in the range multiply to form this
//palindrome
else
{
    working--;
}

Can someone point me in the right direction?

Also, I made a nifty looking flowchart to demonstrate my logic...if that would help anyone help me diagnose my problem, I can send it along (or can I post it here somehow) in PDF or visio format.

Thanks,

Vince

[vince1981]

Got it! If anyone is still reading this thread and would care to provide feedback/advice on how I could make the program better/shorter before I mark this as solved, I'd be very greatful.

#include<iostream>
using namespace std;

//determines whether a number is a palindrome
bool ispalindrome (int pal)
{
    int working=pal;
    int numdig=0;
    int counter;

    //determines how many digits are in pal (verified that this works)
/*    numdig=numberdigits(working);*/

while (working>0)
    {
        working=(working-(working%10))/10;
        numdig++;
    }
    
   //creates an array with counter elements and writes the digits of working
   //into the array (verified that this works)
   counter=numdig;
   working=pal;
   int palcheck[counter];    
   for (;counter>=1; counter--)
   {
        palcheck[counter-1]=working%10;
        working=(working-(working%10))/10;
   }
   
     //compares the corresponding elements of the array to determine if they are
    //equal
    int counter2=numdig-1;
    counter=0;
    bool movingon=false;
    
    do
    {
        if (palcheck[counter]!=palcheck[counter2])
        {
            movingon=true;
            return(false);
        }

        else if (palcheck[counter]==palcheck[counter2], counter<counter2)
        {
            counter++;
            counter2--;
        }
            
        if (palcheck[counter]==palcheck[counter2], counter>=counter2)
        {
            movingon=true;
            return(true);
        }
    }
    
    while (movingon==false);
}

int main ()
{
    int low=0, high=0, working;
    bool progcomplete=false;
    

    //Program's purpose
    cout<<"What is the largest palindrome formed by multiplying two numbers";
    cout<<" from a given "<<endl<<"range?"<<endl<<endl;
    
    //Gets the lowest number in the range
    cout<<"Enter the lowest number in range."<<endl;
    cin>>low;
    cout<<endl;
    
    //Gets the highest number in the range
    cout<<"Enter the highest number in the range."<<endl;
    cin>>high;
    cout<<endl;
    
    cout<<"The palindrome must be between "<<low*low<<" and "<<high*high<<"."<<endl<<endl;

    int factor1=high, factor2=low;    
    
    //Start checking for palindromes, beginning with the largest candidate
    working=high*high;
    
    while (progcomplete==false)
        {
            factor1=high;
            factor2=low;
            //1. working must be >= low^2 or any palindromes found will be outside
            //the specified range 
            if (working>=low*low)
            {
                //2. is working a palindrome?
                if (ispalindrome(working)==true)
                {   
                    //3. factor1 must be >= low or any palindromes will be outside
                    //the specified range
                    for (; factor1>=low; factor1--)
                    {   
                        //4. factor divides evenly into working and is within
                        //the specified range
                        if (working%factor1==0)
                        {
                            //cout<<factor1<<" is a factor of "<<working<<"."<<endl;
                            //system("pause");
                            
                            //initialize factor2 to determine if it's within
                            //the specified range
                            factor2=working/factor1;
                            
                            //5. factor1 is within specified range; if factor2
                            //is as well, working is the palindrome the program
                            //is trying to find
                            if (working%factor2==0, factor2>=low, factor2<=high)
                            {   
                                cout<<"The largest palindrome that is the ";
                                cout<<"product of two numbers found in the "<<endl;
                                cout<<"specified range is: "<<working<<"."<<endl<<endl;
                                cout<<"It is the product of "<<factor2<<" and ";
                                cout<<factor1<<"."<<endl<<endl;
                                
                                system("pause");
                                
                                progcomplete=true;
                                break;
                            }
                        }
                    }

                    //all numbers in the range have been tested, and none are
                    //factors of working; increment working to test the next
                    //number
                    working--;
                }
                
                //2. working is not a palindrome; increment and reiterate
                else
                {
                    working--;
                }
            }
            
            //1. working has dropped below the specified range; terminate program
            else
            {
                cout<<"No two of the numbers in your range can be multiplied ";
                cout<<"together to make a palindrome."<<endl;
                progcomplete=true;                
            }
        }
    return(0);
}

[ne555]

Again, this is illegal:

   counter=numdig;
   working=pal;
   int palcheck[counter]; //ISO C++ forbids variable length array. 

Use a std::vector (or dynamic allocation)

if (palcheck[counter]==palcheck[counter2], counter>=counter2)
if (working%factor2==0, factor2>=low, factor2<=high)

IIRC the comma operator will return the result of the rightmost operation. I think that is not what you want.

working=(working-(working%10))/10; is equivalent to working /= 10;

¿What is the purpose of movingon? you return just after you set it to a value. The same could be told about progcomplete.

_Don't use system:
http://www.cplusplus.com/forum/articles/11153/
http://www.cplusplus.com/forum/articles/7312/

_Try to modularise more.
__A function that counts the number of digits.
__Another to make the conversion number->array.
__Another to make the check.

_Test another methods. By instance:

bool is_palind( int n ){
  int rev = reverse(n); //don't use arrays in that function
  return n == rev;
}

_I found confusing counter and counter2, will prefer left and right.

_You will decrement working, it does not matter that it is a palindrome or not.
Also the comments say that you increment it.

progcomplete==false That variable is a Boolean, just check its value. if( var ) or if( not var )

Regards