Member Avatar for arun_lisieux

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
  • 90 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by arun_lisieux
Member Avatar for Comatose

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?

Member Avatar for 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?

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.

Member Avatar for Comatose

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)

Member Avatar for arun_lisieux

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.

#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 << "\nElement " << delete_value << "not found" << endl;
				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";
}
Member Avatar for StuXYZ

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.

Member Avatar for arun_lisieux

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.