PROBLEM :

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

I came up with a solution for the above problem. I used a linked list to save the digits, compare them to find palindromes. If found as palindromes, the are pushed into a vector and the whole vector is displayed in the last.

PS : As the list functions will occupy lots of space, im not posting the list functions here.

``````#include <iostream>
#include <vector>

using namespace std;

vector<int> palindromes;
vector<int>::iterator it;

struct llist
{
int value;
llist *next;
};

llist *start = NULL;

void insert(int);
void delete_list();
void disp();
bool is_pal();

bool is_pal() /* List Function to check for palindromes*/
{
int d[6], i=0;//, count = 0;
llist *temp;
temp = start;
while (temp->next != NULL)
{
d[i] = temp->value;
i++;
//count++;
temp = temp->next;
}
d[i] = temp->value;
//count++;

//cout << "No of digits in the no : " << count << endl;

if ( (d[0]==d[5]) && (d[1]==d[4]) && (d[2]==d[3]) )
return true;

delete_list();
}

class palindrome
{
public:
int stand;

void product();
void is_palindrome(int);
};

void palindrome:: product()
{
stand = 999;
int temp = 999;
int prod = 1;
while (stand>100)
{
while (temp>100)
{
prod = stand * temp;
//cout << "No Tested : " << prod << endl;
is_palindrome(prod);
temp--;
}
stand--;
}
}

void palindrome:: is_palindrome(int x)
{
int r, t;
t = x;
bool flag;

while (t>=10)
{
r = t%10;
insert(r);
t /= 10;
}
insert(t);
//cout << "Digits in the number : ";
//disp();
cout << "\n\n";
flag = is_pal();

if (flag==true)
{
palindromes.push_back(x);
//cout << "\n" << x << endl;
}
}

int main()
{
palindrome inst;
inst.product();
cout << "Palindromes\n\n";
for (it = palindromes.begin(); it != palindromes.end(); it++)
cout << (*it) << endl;
cout << "\n\n";
}``````
3
Contributors
6
Replies
7
Views
9 Years
Discussion Span
Last Post by arun_lisieux

So, what I gather is you have a problem.... the solution to the problem.... and you are posting here because you have temporarily gone insane?

So, what I gather is you have a problem.... the solution to the problem.... and you are posting here because you have temporarily gone insane?

If i had the solution, i wouldn't be posting here would i? ;) I tried to solve that problem and came up with a code. The code doesnt have any syntax errors, compiles with a single warning. But im not getting the desired output. So, i wanted to know where i have went wrong. Can you kindly point out where i have made a mistake?

EDIT : Oops! Sorry, i forgot to mention in the message part that my code doesnt work properly as i have mentioned that in the subject.

ok, can you attach your code for the list handling (instead of posting it as code, you can attach it to the post as a file in advanced mode)

ok, can you attach your code for the list handling (instead of posting it as code, you can attach it to the post as a file in advanced mode)

Ok, I will attach the whole file along with this post.

Attachments
``````#include <iostream>
#include <vector>

using namespace std;

vector<int> palindromes;
vector<int>::iterator it;

struct llist
{
int value;
llist *next;
};

llist *start = NULL;

void insert(int);
//void delete_start();
//void delete_end();
//void delete_middle(int);
void delete_list();
void disp();
bool is_pal();

void insert (int insert_value)/* List Function to insert a value at the end of the list*/
{
llist *temp, *temp1;

temp = new llist;
temp->value = insert_value;
temp->next = NULL;

if (start == NULL)
start = temp;

else
{
temp1 = start;
while (temp1->next != NULL)
temp1 = temp1->next;
temp1->next = temp;
}
}

/*void delete_start()
{
llist *temp;

temp = start;
start = start->next;
delete temp;
}

void delete_end()
{
llist *temp, *temp1;

if (start == NULL)
cout << "Empty List" << endl;
else
{
temp1 = start;
if (temp1->next == NULL)
{
delete temp1;
start = NULL;
}

else
{
while (temp1->next != NULL)
{
temp = temp1;
temp1 = temp1->next;
}
delete temp1;
temp->next = NULL;
}
}
}

void delete_middle(int delete_value)
{
llist *temp, *temp1;

if (start == NULL)
cout << "Empty List" << endl;
else
{
temp1 = start;
if (temp1->next == NULL)
{
if (temp1->value == delete_value)
{
delete temp1;
start = NULL;
}

else
cout << "";
}

else
{
//temp = temp1;
while (temp1->value != delete_value && temp1->next != NULL)
{
temp = temp1;
temp1 = temp1->next;
}

if (temp1->next == NULL)
{
if (temp1->value == delete_value)
{
temp->next = NULL;
delete temp1;
}

else
//cout << "\nElement " << delete_value << " not found" << endl;
cout << "";
}

else
{
temp->next = temp1->next;
delete temp1;
}
}
}
}*/

void delete_list() /* List Function to delete the whole list*/
{
llist *temp;

if (start == NULL)
cout << "Empty List" << endl;
else
{
temp = start;
if (temp->next == NULL)
{
delete temp;
start = NULL;
}

else
{
while (temp->next != NULL)
{
llist *temp1;
temp1 = temp;
temp = temp->next;
delete temp1;
}
delete temp;
start = NULL;
}
}
}

void disp()/* List Function to display elements of the list*/
{
llist *temp;

if (start == NULL)
{
cout << "\nList is Empty" << endl;
}

else
{
temp = start;
if (temp->next == NULL)
cout << temp->value;
else
{
while (temp->next != NULL)
{
cout << temp->value << "\t";
temp = temp->next;
}
cout << temp->value << endl;
cout << "\n";
}
}
}

bool is_pal()/* List Function to check for palindromes*/
{
int d[6], i=0;//, count = 0;
llist *temp;
temp = start;
while (temp->next != NULL)
{
d[i] = temp->value;
i++;
//count++;
temp = temp->next;
}
d[i] = temp->value;
//count++;

//cout << "No of digits in the no : " << count << endl;

if ( (d[0]==d[5]) && (d[1]==d[4]) && (d[2]==d[3]) )
return true;

delete_list();
}
class palindrome

{
public:
int stand;

void product();
void is_palindrome(int);
};

void palindrome:: product()
{
stand = 999;
int temp = 999;
int prod = 1;
while (stand>100)
{
while (temp>100)
{
prod = stand * temp;
//cout << "No Tested : " << prod << endl;
is_palindrome(prod);
temp--;
}
stand--;
}
}

void palindrome:: is_palindrome(int x)
{
int r, t;
t = x;
bool flag;

while (t>=10)
{
r = t%10;
insert(r);
t /= 10;
}
insert(t);
//cout << "Digits in the number : ";
//disp();
cout << "\n\n";
flag = is_pal();

if (flag==true)
{
palindromes.push_back(x);
//cout << "\n" << x << endl;
}
}

int main()
{
palindrome inst;
inst.product();
cout << "Palindromes\n\n";
for (it = palindromes.begin(); it != palindromes.end(); it++)
cout << (*it) << endl;
cout << "\n\n";
}``````

Help!!!!!! -- This is awful / Where to start!!

Ok consider this:
999*999 is 998001
So count down from that number. Then if you find a palindrom then find the lowest factor. (simple loop works). - -
Divide the number by that factor and repeat.
You will need to keep a multiple of the factors found (Imult)
When Imult gets to between 100 and 1000 check that the cofactor is also between 100 and 1000.
If that is the case then you have finished.

I will also say consider this:

``````bool isPal(int N)
{
const int NP=std::log10(N);
int Nx(static_cast<int>(std::pow(10.0,NP)));
while (Nx && ((N % 10) == (N/Nx)))
{
N -= (N/Nx)*Nx;
N /= 10;
Nx /= 100;
}
return (N>=1) ? 0 : 1;
}``````

Does that not find the palindroms with significantly less effort,

The algorithm also is scalable to the long int limit. (can't be bothered to test it further.) What has changed is that the palindromes are much much more limited than the set of multiple produces.

Always be very very aware that marks are handed out for (a) clean code and (b) scalability.

Help!!!!!! -- This is awful / Where to start!!

Ok consider this:
999*999 is 998001
So count down from that number. Then if you find a palindrom then find the lowest factor. (simple loop works). - -
Divide the number by that factor and repeat.
You will need to keep a multiple of the factors found (Imult)
When Imult gets to between 100 and 1000 check that the cofactor is also between 100 and 1000.
If that is the case then you have finished.

I will also say consider this:

``````bool isPal(int N)
{
const int NP=std::log10(N);
int Nx(static_cast<int>(std::pow(10.0,NP)));
while (Nx && ((N % 10) == (N/Nx)))
{
N -= (N/Nx)*Nx;
N /= 10;
Nx /= 100;
}
return (N>=1) ? 0 : 1;
}``````

Does that not find the palindroms with significantly less effort,

The algorithm also is scalable to the long int limit. (can't be bothered to test it further.) What has changed is that the palindromes are much much more limited than the set of multiple produces.

Always be very very aware that marks are handed out for (a) clean code and (b) scalability.

Thanks again dude. Will get back to you after trying out your method.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.