Longest Palindrome In An Array In C Program

In an array of numbers, identifying specific patterns is a common task. One such pattern is the palindrome, a number that reads the same forwards and backward. The challenge often lies in not just finding palindromes, but locating the "longest" one, typically referring to the number with the most digits.

In this article, you will learn how to efficiently identify palindromic numbers within an array and determine the one with the maximum number of digits using C programming.

Problem Statement

A palindrome is a number (or word) that remains the same when its digits are reversed. For example, 121, 4554, and 7 are palindromes. Given an array of integers, the goal is to find the integer within that array which is a palindrome and possesses the greatest number of digits. If no palindromes are found, or if multiple palindromes share the maximum digit count, the program should clearly indicate this.

This problem is relevant in areas requiring data validation, number pattern analysis, and solving specific number theory puzzles where numbers with symmetrical properties are significant.

Example

Consider the following array of integers: int numbers[] = {121, 23, 4554, 9, 78987, 1001, 5, 987654321};

The expected output for the longest palindrome would be 78987, as it is a palindrome and has 5 digits, which is the maximum among the palindromes in the array.

Background & Knowledge Prerequisites

To understand and implement the solutions effectively, readers should be familiar with:

• Basic C syntax: Variables, data types, and fundamental operators.
• Control flow: for and while loops, if-else conditional statements.
• Functions: Defining and calling functions.
• Integer arithmetic: Operators such as modulo (%) for getting the last digit and division (/) for removing the last digit.
• Arrays: Declaring, initializing, and iterating through them.

Use Cases or Case Studies

1. Data Validation Systems: In applications where numerical input needs to conform to specific patterns, identifying palindromic numbers can be a validation step (e.g., specific ID numbers, transaction codes).
2. Number Theory Investigations: Used in mathematical contexts to explore properties of numbers, such as finding palindromic primes or identifying palindromes in different number bases.
3. Educational Programming Challenges: A common problem in introductory programming courses to teach algorithm design, integer manipulation, and array processing.
4. Game Development: Certain game mechanics or puzzles might involve generating or identifying palindromic sequences or numbers.

Solution Approaches

We will explore two distinct approaches to solve this problem, primarily differing in how they check if a number is a palindrome.

Approach 1: Iterative Digit Reversal for Palindrome Check

This approach involves reversing a number digit by digit and then comparing the reversed number with the original. It's an efficient method that relies purely on integer arithmetic.

• One-line summary: Reverses the input number using arithmetic operations and compares it to the original to determine if it's a palindrome.

// Longest Palindrome in Array (Iterative Digit Reversal)
#include <stdio.h>
#include <limits.h> // For INT_MIN

// Function to check if a number is a palindrome
// Returns 1 if palindrome, 0 otherwise
int isPalindrome(int num) {
    // Negative numbers are not typically considered palindromes
    // Single digit numbers (0-9) are palindromes
    if (num < 0) {
        return 0;
    }
    if (num >= 0 && num <= 9) {
        return 1;
    }

    int originalNum = num;
    int reversedNum = 0;

    // Step 1: Reverse the number
    while (num > 0) {
        int digit = num % 10;
        reversedNum = reversedNum * 10 + digit;
        num /= 10;
    }

    // Step 2: Compare the original number with the reversed number
    return originalNum == reversedNum;
}

// Function to count the number of digits in an integer
int countDigits(int num) {
    if (num == 0) {
        return 1;
    }
    int count = 0;
    // Handle negative numbers by converting to positive for digit counting
    if (num < 0) {
        num = -num;
    }
    while (num > 0) {
        num /= 10;
        count++;
    }
    return count;
}

int main() {
    int numbers[] = {121, 23, 4554, 9, 78987, 1001, 5, 987654321, 0, -121};
    int n = sizeof(numbers) / sizeof(numbers[0]);

    int longestPalindrome = INT_MIN; // Initialize with a value indicating no palindrome found
    int maxDigits = -1;
    int foundPalindrome = 0;

    printf("Array elements: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", numbers[i]);
    }
    printf("\\n\\n");

    // Step 1: Iterate through each number in the array
    for (int i = 0; i < n; i++) {
        int currentNum = numbers[i];

        // Step 2: Check if the current number is a palindrome
        if (isPalindrome(currentNum)) {
            foundPalindrome = 1;
            int currentDigits = countDigits(currentNum);

            // Step 3: If it's a palindrome, compare its digit count with the maximum found so far
            if (currentDigits > maxDigits) {
                maxDigits = currentDigits;
                longestPalindrome = currentNum;
            }
        }
    }

    // Step 4: Print the result
    if (foundPalindrome) {
        printf("The longest palindrome in the array is: %d\\n", longestPalindrome);
        printf("It has %d digits.\\n", maxDigits);
    } else {
        printf("No palindromes found in the array.\\n");
    }

    return 0;
}

Run

• Sample Output:

Array elements: 121 23 4554 9 78987 1001 5 987654321 0 -121 

The longest palindrome in the array is: 78987
It has 5 digits.

• Stepwise Explanation:

1. isPalindrome(int num) function:
   • It first handles edge cases: negative numbers are not considered palindromes, and single-digit numbers (0-9) are.

1. countDigits(int num) function:
   • Handles the case for 0 separately, which has 1 digit.

1. main() function:
   • Initializes longestPalindrome to INT_MIN (or a similar indicator) and maxDigits to -1 to ensure any found palindrome will be considered longer. A foundPalindrome flag tracks if at least one palindrome has been encountered.

Approach 2: String Conversion and Two-Pointer Comparison

This approach converts each integer into a string. Checking for a palindrome then becomes a string manipulation problem, using a two-pointer technique.

• One-line summary: Converts the integer to a string and then uses two pointers (one from the start, one from the end) to compare characters for palindromic property.

// Longest Palindrome in Array (String Conversion)
#include <stdio.h>
#include <string.h> // For strlen
#include <stdlib.h> // For malloc, free
#include <limits.h> // For INT_MIN

// Function to check if a string is a palindrome
// Returns 1 if palindrome, 0 otherwise
int isPalindromeString(char *str) {
    int length = strlen(str);
    int start = 0;
    int end = length - 1;

    // Step 1: Use two pointers to compare characters from both ends
    while (start < end) {
        if (str[start] != str[end]) {
            return 0; // Not a palindrome
        }
        start++;
        end--;
    }
    return 1; // It is a palindrome
}

int main() {
    int numbers[] = {121, 23, 4554, 9, 78987, 1001, 5, 987654321, 0, -121};
    int n = sizeof(numbers) / sizeof(numbers[0]);

    int longestPalindrome = INT_MIN;
    int maxDigits = -1;
    int foundPalindrome = 0;

    // Max digits an int can have (for 32-bit int, ~10 digits + sign + null terminator)
    // For long long, it could be up to 20 digits. Let's use 15 for safety.
    char numStr[15]; 

    printf("Array elements: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", numbers[i]);
    }
    printf("\\n\\n");

    // Step 1: Iterate through each number in the array
    for (int i = 0; i < n; i++) {
        int currentNum = numbers[i];

        // Step 2: Convert the number to a string
        // sprintf returns the number of characters written, which is the length
        // Handle negative numbers explicitly: negative numbers like -121 would become "-121"
        // which won't be a palindrome as a string.
        if (currentNum < 0) {
            continue; // Skip negative numbers as they are not palindromes by convention
        }
        
        int len = sprintf(numStr, "%d", currentNum);

        // Step 3: Check if the string representation is a palindrome
        if (isPalindromeString(numStr)) {
            foundPalindrome = 1;

            // Step 4: If it's a palindrome, compare its length with the maximum found so far
            if (len > maxDigits) {
                maxDigits = len;
                longestPalindrome = currentNum;
            }
        }
    }

    // Step 5: Print the result
    if (foundPalindrome) {
        printf("The longest palindrome in the array is: %d\\n", longestPalindrome);
        printf("It has %d digits.\\n", maxDigits);
    } else {
        printf("No palindromes found in the array.\\n");
    }

    return 0;
}

Run

• Sample Output:

Array elements: 121 23 4554 9 78987 1001 5 987654321 0 -121 

The longest palindrome in the array is: 78987
It has 5 digits.

• Stepwise Explanation:

1. isPalindromeString(char *str) function:
   • Calculates the length of the input string.

1. main() function:
   • Similar to Approach 1, it initializes longestPalindrome, maxDigits, and foundPalindrome.

Conclusion

Finding the longest palindrome in an array involves two primary steps: checking if a number is a palindrome and then comparing the lengths of the identified palindromes. Both the iterative digit reversal (Approach 1) and string conversion (Approach 2) methods effectively determine if a number is a palindrome. The iterative digit reversal approach uses integer arithmetic, making it generally more memory-efficient and faster for large numbers as it avoids string allocation. The string conversion approach, while potentially using more memory, can be more readable for those accustomed to string manipulation and offers a direct way to get the number of digits (string length). The choice between approaches often depends on performance requirements, memory constraints, and personal coding style.

Summary

• Palindrome Definition: A number that reads the same forwards and backward.
• Problem Objective: Identify the palindrome with the most digits in an integer array.
• Approach 1 (Iterative Digit Reversal):
• Reverses the number using modulo and division.
• Compares the reversed number to the original.
• Highly efficient for integer palindrome checks.
• Approach 2 (String Conversion):
• Converts the number to its string representation.
• Uses a two-pointer technique to check for string palindrome.
• Offers clarity and direct length measurement (string length).
• Key Considerations: Handling negative numbers (typically not palindromes), single-digit numbers (always palindromes), and arrays containing no palindromes.