How to ?

[Simjeff]

Hello im having a little problem. I need to make a program in which i enter a number between 3 and 1000 and make an array with that many elements in it . Then i need to see how many palindromes are there in that array. I get that you need a for or while and count++ for every palindrome but i dont know how to structure it.

For example if you write down 9 and then the 9 elements are 7 7 7 9 8 9 7 7 7 it should cout 3. ( 777 is a palindrome , 989 is a palindrome and 777989777 is a palindrome.)

[MikeyBoy]

Simjeff wrote:

Hello im having a little problem. I need to make a program in which i enter a number between 3 and 1000 and make an array with that many elements in it . Then i need to see how many palindromes are there in that array. I get that you need a for or while and count++ for every palindrome but i dont know how to structure it.

For example if you write down 9 and then the 9 elements are 7 7 7 9 8 9 7 7 7 it should cout 3. ( 777 is a palindrome , 989 is a palindrome and 777989777 is a palindrome.)

No, the answer would not be 3.

77
79897
7798977

are all also palindromes. Also, 777 appears twice, so should register as 2 palindromes. 77 appears 4 times, so should register as 4 palindromes

The algorithm that occurs to me off the top of my head is:

- Iterate over every element of the array
- For each iteration, iterate from that element to the nearest end of the array, so that you're iterating over every possible length for which the element might be the centre of a palindrome.
- For each inner iteration, determine whether the element is the centre of a palindrome of that length.

(Edited to clarify the structure, because my formatting didn't work.)


Note that the last part will work differently depending on whether you're looking at an even-length palindrome, or an odd-length one.

[Simjeff]

i should correct myself . I forgot to mention it has to be a minimum of 3 numbers and repeatable palindromes do not count, so 77 and the second 777 do not count.

[MikeyBoy]

i should correct myself . I forgot to mention it has to be a minimum of 3 numbers and repeatable palindromes do not count, so 77 and the second 777 do not count.

OK, but that doesn't change my proposed algorithm in any significant way. It just means the result should be 5, yes?

[Simjeff]

i suppose so , i just dont know how to iterate xD

[MikeyBoy]

Just use a simple for loop. Or a while loop, if you prefer.

[lastchance]

#include <iostream>
#include <string>
#include <set>
using namespace std;


bool isPalindromeSubstring( const string &str, int p, int q )
{
   if ( q < p ) return true;
   return str[p] == str[q] && isPalindromeSubstring( str, p + 1, q - 1 );
}


set<string> palindromes( const string &str, int minLength )
{
   set<string> result;
   int N = str.size();
   for ( int len = minLength; len <= N; len++ )
   {
      for ( int i = 0; i <= N - len; i++ ) if ( isPalindromeSubstring( str, i, i + len - 1 ) ) result.insert( str.substr( i, len ) );
   }
   return result;
}


int main()
{
   string test = "777989777";
   int minLength = 3;
   set<string> pals = palindromes( test, minLength );
   cout << test << " has " << pals.size() << " sub-palindromes of length at least " << minLength << ". These are:\n";
   for ( const string &s : pals ) cout << s << '\n';
}

777989777 has 5 sub-palindromes of length at least 3. These are:
777
777989777
7798977
79897
989