Posted on by Kalkicode
Code Mathematics

Find the next smallest palindrome in an array

The given problem revolves around finding the next smallest palindrome in an array of digits. A palindrome is a sequence that reads the same forwards as it does backwards. The challenge here is to modify the given array of digits to generate the smallest palindrome that is greater than the given number.

Problem Statement

Given an array of digits representing a number, the goal is to find the next smallest palindrome by making changes to the digits.

Example

Let's consider the input array digits1 = {2, 0, 2}.

The current number represented by this array is 202. The next smallest palindrome greater than 202 is 212. So, we need to modify the array to become {2, 1, 2}.

Idea to Solve the Problem

To solve this problem, we can follow these steps:

  1. Check if the input array contains all 9's. If yes, then the next smallest palindrome would be a number with a leading 1 followed by all 0's and a trailing 1. For example, if the input is all 9's, the output will be 100...001.
  2. If the input array contains only a single digit, increment it by 1 and return the result. For example, if the input is 9, the output will be 10.
  3. If the input array is already a palindrome, then we need to adjust the middle digits and propagate any carry to the adjacent digits.
  4. If the input array is not a palindrome, we need to increment the left half of the array and mirror it to the right half.

Pseudocode

Here's the pseudocode for the algorithm:

nextPalindrome(digits[], n):
    if all elements in digits are 9:
        print 1 followed by (n-1) zeros followed by 1
    else if n is 1:
        increment digits[0] by 1
        print the modified digits array
    else:
        mid = n / 2
        carry = 0
        left = mid - 1
        right = mid + 1
        if n is even:
            if digits[left] <= digits[right]:
                carry = 1
        else:
            increment digits[mid] by 1
            carry = digits[mid] / 10
            if carry is not 0:
                digits[mid] = 0
        
        while left >= 0:
            if digits[left] == 9 and carry == 1:
                digits[left] = 0
                digits[right] = 0
            else:
                digits[left] = digits[left] + carry
                digits[right] = digits[left]
                carry = 0
            decrement left
            increment right
        
        print the modified digits array

Algorithm Explanation

  1. We start by checking if all elements in the array are 9. If yes, we print the result as a palindrome consisting of 1 followed by (n-1) zeros followed by another 1.
  2. If n is 1, we increment the single digit by 1 and print the result.
  3. If the array is not all 9's and not of length 1, we proceed with the palindrome generation process:
    • We initialize a variable mid to hold the index of the middle element.
    • We initialize a carry variable to track if there's a carry from the middle digit.
    • We set left and right pointers to navigate through the left and right halves of the array.
    • If the array length is even, we compare the left and right digits. If the left digit is smaller or equal to the right digit, we set the carry to 1.
    • If the array length is odd, we increment the middle digit and calculate the carry. If the carry is not zero, we set the middle digit to 0.
    • We iterate through the left half of the array, adjusting digits based on the carry and mirroring the changes to the right half.
  4. Finally, we print the modified digits array.

Program Solution

// C program for 
// Find the next smallest palindrome in an array 
#include <stdio.h>

// Display given digits
void printResult(int digits[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf(" %d", digits[i]);
	}
	printf("\n");
}
// Handles the request of finding next palindrome
void nextPalindrome(int digits[], int n)
{
	int i = 0;
	// Check that all 9 present in given array
	for (i = 0; i < n; ++i)
	{
		if (digits[i] != 9)
		{
			// When element is not 9
			i = n + 1;
		}
	}
	if (i == n)
	{
		// When have series of 9..99.. 
		// Display result
		for (i = 0; i <= n; ++i)
		{
			if (i == 0 || i == n)
			{
				printf(" 1");
			}
			else
			{
				printf(" 0");
			}
		}
		printf("\n");
	}
	else if (n == 1)
	{
		// When have single digit palindrome
		// Because its digit array
		printf(" %d\n", digits[0] + 1);
	}
	else
	{
		// When array is form of palindrome
		// Define some useful auxiliary variables
		int mid = n / 2;
		int carry = 0;
		int left = mid - 1;
		int right = mid + 1;
		if (n % 2 == 0)
		{
			right = mid;
			if (digits[left] <= digits[right])
			{
				// When have need to include carry
				carry = 1;
			}
		}
		else
		{
			digits[mid] += 1;
			// Calculate carry
			carry = digits[mid] / 10;
			if (carry != 0)
			{
				// When middle element is overflow
				digits[mid] = 0;
			}
		}
		// Equal the left part to right part, 
		// And include carry when need
		while (left >= 0)
		{
			if (digits[left] == 9 && carry == 1)
			{
				// When central element is 9
				// Set zero
				digits[left] = 0;
				digits[right] = 0;
			}
			else
			{
				// Set left element to right part
				digits[left] = digits[left] + carry;
				digits[right] = digits[left];
				// reset the carry
				carry = 0;
			}
			// Change index location
			left--;
			right++;
		}
		printResult(digits, n);
	}
}
int main(int argc, char
	const *argv[])
{
	// Define array of positive digits
	int digits1[] = {
		1 , 9 , 1
	};
	int digits2[] = {
		1 , 2 , 3 , 4 , 1
	};
	int digits3[] = {
		1 , 1 , 1 , 1 , 1 , 1 , 1 , 1
	};
	int digits4[] = {
		9 , 9 , 9 , 9 , 9 , 9 , 9
	};
	int digits5[] = {
		2 , 0 , 7 , 8 , 2 , 2
	};
	int digits6[] = {
		2 , 0 , 7 , 4 , 2 , 2
	};
	// Test A
	int n = sizeof(digits1) / sizeof(digits1[0]);
	nextPalindrome(digits1, n);
	// Test B
	n = sizeof(digits2) / sizeof(digits2[0]);
	nextPalindrome(digits2, n);
	// Test C
	n = sizeof(digits3) / sizeof(digits3[0]);
	nextPalindrome(digits3, n);
	// Test D
	n = sizeof(digits4) / sizeof(digits4[0]);
	nextPalindrome(digits4, n);
	// Test E
	n = sizeof(digits5) / sizeof(digits5[0]);
	nextPalindrome(digits5, n);
	// Test G
	n = sizeof(digits6) / sizeof(digits6[0]);
	nextPalindrome(digits6, n);
	return 0;
}

input

 2 0 2
 1 2 4 2 1
 1 1 1 2 2 1 1 1
 1 0 0 0 0 0 0 1
 2 0 8 8 0 2
 2 0 7 7 0 2
/*
  Java Program for
  Find the next smallest palindrome in an array 
*/
public class Palindrome
{
	// Display given digits
	public void printResult(int[] digits, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			System.out.print(" " + digits[i]);
		}
		System.out.print("\n");
	}
	// Handles the request of finding next palindrome
	public void nextPalindrome(int[] digits, int n)
	{
		int i = 0;
		// Check that all 9 present in given array
		for (i = 0; i < n; ++i)
		{
			if (digits[i] != 9)
			{
				// When element is not 9
				i = n + 1;
			}
		}
		if (i == n)
		{
			// When have series of 9..99.. 
			// Display result
			for (i = 0; i <= n; ++i)
			{
				if (i == 0 || i == n)
				{
					System.out.print(" 1");
				}
				else
				{
					System.out.print(" 0");
				}
			}
			System.out.print("\n");
		}
		else if (n == 1)
		{
			// When have single digit palindrome
			// Because its digit array
			System.out.print(" " + digits[0] + 1 + "\n");
		}
		else
		{
			// When array is form of palindrome
			// Define some useful auxiliary variables
			int mid = n / 2;
			int carry = 0;
			int left = mid - 1;
			int right = mid + 1;
			if (n % 2 == 0)
			{
				right = mid;
				if (digits[left] <= digits[right])
				{
					// When have need to include carry
					carry = 1;
				}
			}
			else
			{
				digits[mid] += 1;
				// Calculate carry
				carry = digits[mid] / 10;
				if (carry != 0)
				{
					// When middle element is overflow
					digits[mid] = 0;
				}
			}
			// Equal the left part to right part, 
			// And include carry when need
			while (left >= 0)
			{
				if (digits[left] == 9 && carry == 1)
				{
					// When central element is 9
					// Set zero
					digits[left] = 0;
					digits[right] = 0;
				}
				else
				{
					// Set left element to right part
					digits[left] = digits[left] + carry;
					digits[right] = digits[left];
					// reset the carry
					carry = 0;
				}
				// Change index location
				left--;
				right++;
			}
			printResult(digits, n);
		}
	}
	public static void main(String[] args)
	{
		Palindrome task = new Palindrome();
		// Define array of positive digits
		int[] digits1 = {
			1 , 9 , 1
		};
		int[] digits2 = {
			1 , 2 , 3 , 4 , 1
		};
		int[] digits3 = {
			1 , 1 , 1 , 1 , 1 , 1 , 1 , 1
		};
		int[] digits4 = {
			9 , 9 , 9 , 9 , 9 , 9 , 9
		};
		int[] digits5 = {
			2 , 0 , 7 , 8 , 2 , 2
		};
		int[] digits6 = {
			2 , 0 , 7 , 4 , 2 , 2
		};
		// Test A
		int n = digits1.length;
		task.nextPalindrome(digits1, n);
		// Test B
		n = digits2.length;
		task.nextPalindrome(digits2, n);
		// Test C
		n = digits3.length;
		task.nextPalindrome(digits3, n);
		// Test D
		n = digits4.length;
		task.nextPalindrome(digits4, n);
		// Test E
		n = digits5.length;
		task.nextPalindrome(digits5, n);
		// Test G
		n = digits6.length;
		task.nextPalindrome(digits6, n);
	}
}

input

 2 0 2
 1 2 4 2 1
 1 1 1 2 2 1 1 1
 1 0 0 0 0 0 0 1
 2 0 8 8 0 2
 2 0 7 7 0 2
// Include header file
#include <iostream>
using namespace std;
/*
  C++ Program for
  Find the next smallest palindrome in an array 
*/
class Palindrome
{
	public:
		// Display given digits
		void printResult(int digits[], int n)
		{
			for (int i = 0; i < n; ++i)
			{
				cout << " " << digits[i];
			}
			cout << "\n";
		}
	// Handles the request of finding next palindrome
	void nextPalindrome(int digits[], int n)
	{
		int i = 0;
		// Check that all 9 present in given array
		for (i = 0; i < n; ++i)
		{
			if (digits[i] != 9)
			{
				// When element is not 9
				i = n + 1;
			}
		}
		if (i == n)
		{
			// When have series of 9..99.. 
			// Display result
			for (i = 0; i <= n; ++i)
			{
				if (i == 0 || i == n)
				{
					cout << " 1";
				}
				else
				{
					cout << " 0";
				}
			}
			cout << "\n";
		}
		else
		{
			if (n == 1)
			{
				// When have single digit palindrome
				// Because its digit array
				cout << " " << digits[0] + 1 << "\n";
			}
			else
			{
				// When array is form of palindrome
				// Define some useful auxiliary variables
				int mid = n / 2;
				int carry = 0;
				int left = mid - 1;
				int right = mid + 1;
				if (n % 2 == 0)
				{
					right = mid;
					if (digits[left] <= digits[right])
					{
						// When have need to include carry
						carry = 1;
					}
				}
				else
				{
					digits[mid] += 1;
					// Calculate carry
					carry = digits[mid] / 10;
					if (carry != 0)
					{
						// When middle element is overflow
						digits[mid] = 0;
					}
				}
				// Equal the left part to right part, 
				// And include carry when need
				while (left >= 0)
				{
					if (digits[left] == 9 && carry == 1)
					{
						// When central element is 9
						// Set zero
						digits[left] = 0;
						digits[right] = 0;
					}
					else
					{
						// Set left element to right part
						digits[left] = digits[left] + carry;
						digits[right] = digits[left];
						// reset the carry
						carry = 0;
					}
					// Change index location
					left--;
					right++;
				}
				this->printResult(digits, n);
			}
		}
	}
};
int main()
{
	Palindrome *task = new Palindrome();
	// Define array of positive digits
	int digits1[] = {
		1 , 9 , 1
	};
	int digits2[] = {
		1 , 2 , 3 , 4 , 1
	};
	int digits3[] = {
		1 , 1 , 1 , 1 , 1 , 1 , 1 , 1
	};
	int digits4[] = {
		9 , 9 , 9 , 9 , 9 , 9 , 9
	};
	int digits5[] = {
		2 , 0 , 7 , 8 , 2 , 2
	};
	int digits6[] = {
		2 , 0 , 7 , 4 , 2 , 2
	};
	// Test A
	int n = sizeof(digits1) / sizeof(digits1[0]);
	task->nextPalindrome(digits1, n);
	// Test B
	n = sizeof(digits2) / sizeof(digits2[0]);
	task->nextPalindrome(digits2, n);
	// Test C
	n = sizeof(digits3) / sizeof(digits3[0]);
	task->nextPalindrome(digits3, n);
	// Test D
	n = sizeof(digits4) / sizeof(digits4[0]);
	task->nextPalindrome(digits4, n);
	// Test E
	n = sizeof(digits5) / sizeof(digits5[0]);
	task->nextPalindrome(digits5, n);
	// Test G
	n = sizeof(digits6) / sizeof(digits6[0]);
	task->nextPalindrome(digits6, n);
	return 0;
}

input

 2 0 2
 1 2 4 2 1
 1 1 1 2 2 1 1 1
 1 0 0 0 0 0 0 1
 2 0 8 8 0 2
 2 0 7 7 0 2
// Include namespace system
using System;
/*
  Csharp Program for
  Find the next smallest palindrome in an array 
*/
public class Palindrome
{
	// Display given digits
	public void printResult(int[] digits, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write(" " + digits[i]);
		}
		Console.Write("\n");
	}
	// Handles the request of finding next palindrome
	public void nextPalindrome(int[] digits, int n)
	{
		int i = 0;
		// Check that all 9 present in given array
		for (i = 0; i < n; ++i)
		{
			if (digits[i] != 9)
			{
				// When element is not 9
				i = n + 1;
			}
		}
		if (i == n)
		{
			// When have series of 9..99.. 
			// Display result
			for (i = 0; i <= n; ++i)
			{
				if (i == 0 || i == n)
				{
					Console.Write(" 1");
				}
				else
				{
					Console.Write(" 0");
				}
			}
			Console.Write("\n");
		}
		else
		{
			if (n == 1)
			{
				// When have single digit palindrome
				// Because its digit array
				Console.Write(" " + digits[0] + 1 + "\n");
			}
			else
			{
				// When array is form of palindrome
				// Define some useful auxiliary variables
				int mid = n / 2;
				int carry = 0;
				int left = mid - 1;
				int right = mid + 1;
				if (n % 2 == 0)
				{
					right = mid;
					if (digits[left] <= digits[right])
					{
						// When have need to include carry
						carry = 1;
					}
				}
				else
				{
					digits[mid] += 1;
					// Calculate carry
					carry = digits[mid] / 10;
					if (carry != 0)
					{
						// When middle element is overflow
						digits[mid] = 0;
					}
				}
				// Equal the left part to right part, 
				// And include carry when need
				while (left >= 0)
				{
					if (digits[left] == 9 && carry == 1)
					{
						// When central element is 9
						// Set zero
						digits[left] = 0;
						digits[right] = 0;
					}
					else
					{
						// Set left element to right part
						digits[left] = digits[left] + carry;
						digits[right] = digits[left];
						// reset the carry
						carry = 0;
					}
					// Change index location
					left--;
					right++;
				}
				this.printResult(digits, n);
			}
		}
	}
	public static void Main(String[] args)
	{
		Palindrome task = new Palindrome();
		// Define array of positive digits
		int[] digits1 = {
			1 , 9 , 1
		};
		int[] digits2 = {
			1 , 2 , 3 , 4 , 1
		};
		int[] digits3 = {
			1 , 1 , 1 , 1 , 1 , 1 , 1 , 1
		};
		int[] digits4 = {
			9 , 9 , 9 , 9 , 9 , 9 , 9
		};
		int[] digits5 = {
			2 , 0 , 7 , 8 , 2 , 2
		};
		int[] digits6 = {
			2 , 0 , 7 , 4 , 2 , 2
		};
		// Test A
		int n = digits1.Length;
		task.nextPalindrome(digits1, n);
		// Test B
		n = digits2.Length;
		task.nextPalindrome(digits2, n);
		// Test C
		n = digits3.Length;
		task.nextPalindrome(digits3, n);
		// Test D
		n = digits4.Length;
		task.nextPalindrome(digits4, n);
		// Test E
		n = digits5.Length;
		task.nextPalindrome(digits5, n);
		// Test G
		n = digits6.Length;
		task.nextPalindrome(digits6, n);
	}
}

input

 2 0 2
 1 2 4 2 1
 1 1 1 2 2 1 1 1
 1 0 0 0 0 0 0 1
 2 0 8 8 0 2
 2 0 7 7 0 2
<?php
/*
  Php Program for
  Find the next smallest palindrome in an array 
*/
class Palindrome
{
	// Display given digits
	public	function printResult($digits, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo " ".$digits[$i];
		}
		echo "\n";
	}
	// Handles the request of finding next palindrome
	public	function nextPalindrome($digits, $n)
	{
		$i = 0;
		// Check that all 9 present in given array
		for ($i = 0; $i < $n; ++$i)
		{
			if ($digits[$i] != 9)
			{
				// When element is not 9
				$i = $n + 1;
			}
		}
		if ($i == $n)
		{
			// When have series of 9..99.. 
			// Display result
			for ($i = 0; $i <= $n; ++$i)
			{
				if ($i == 0 || $i == $n)
				{
					echo " 1";
				}
				else
				{
					echo " 0";
				}
			}
			echo "\n";
		}
		else
		{
			if ($n == 1)
			{
				// When have single digit palindrome
				// Because its digit array
				echo " ".($digits[0] + 1)."\n";
			}
			else
			{
				// When array is form of palindrome
				// Define some useful auxiliary variables
				$mid = (int)($n / 2);
				$carry = 0;
				$left = $mid - 1;
				$right = $mid + 1;
				if ($n % 2 == 0)
				{
					$right = $mid;
					if ($digits[$left] <= $digits[$right])
					{
						// When have need to include carry
						$carry = 1;
					}
				}
				else
				{
					$digits[$mid] += 1;
					// Calculate carry
					$carry = (int)($digits[$mid] / 10);
					if ($carry != 0)
					{
						// When middle element is overflow
						$digits[$mid] = 0;
					}
				}
				// Equal the left part to right part, 
				// And include carry when need
				while ($left >= 0)
				{
					if ($digits[$left] == 9 && $carry == 1)
					{
						// When central element is 9
						// Set zero
						$digits[$left] = 0;
						$digits[$right] = 0;
					}
					else
					{
						// Set left element to right part
						$digits[$left] = $digits[$left] + $carry;
						$digits[$right] = $digits[$left];
						// reset the carry
						$carry = 0;
					}
					// Change index location
					$left--;
					$right++;
				}
				$this->printResult($digits, $n);
			}
		}
	}
}

function main()
{
	$task = new Palindrome();
	// Define array of positive digits
	$digits1 = array(1, 9, 1);
	$digits2 = array(1, 2, 3, 4, 1);
	$digits3 = array(1, 1, 1, 1, 1, 1, 1, 1);
	$digits4 = array(9, 9, 9, 9, 9, 9, 9);
	$digits5 = array(2, 0, 7, 8, 2, 2);
	$digits6 = array(2, 0, 7, 4, 2, 2);
	// Test A
	$n = count($digits1);
	$task->nextPalindrome($digits1, $n);
	// Test B
	$n = count($digits2);
	$task->nextPalindrome($digits2, $n);
	// Test C
	$n = count($digits3);
	$task->nextPalindrome($digits3, $n);
	// Test D
	$n = count($digits4);
	$task->nextPalindrome($digits4, $n);
	// Test E
	$n = count($digits5);
	$task->nextPalindrome($digits5, $n);
	// Test G
	$n = count($digits6);
	$task->nextPalindrome($digits6, $n);
}
main();

input

 2 0 2
 1 2 4 2 1
 1 1 1 2 2 1 1 1
 1 0 0 0 0 0 0 1
 2 0 8 8 0 2
 2 0 7 7 0 2
/*
  Node JS Program for
  Find the next smallest palindrome in an array 
*/
class Palindrome
{
	// Display given digits
	printResult(digits, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write(" " + digits[i]);
		}
		process.stdout.write("\n");
	}
	// Handles the request of finding next palindrome
	nextPalindrome(digits, n)
	{
		var i = 0;
		// Check that all 9 present in given array
		for (i = 0; i < n; ++i)
		{
			if (digits[i] != 9)
			{
				// When element is not 9
				i = n + 1;
			}
		}
		if (i == n)
		{
			// When have series of 9..99.. 
			// Display result
			for (i = 0; i <= n; ++i)
			{
				if (i == 0 || i == n)
				{
					process.stdout.write(" 1");
				}
				else
				{
					process.stdout.write(" 0");
				}
			}
			process.stdout.write("\n");
		}
		else
		{
			if (n == 1)
			{
				// When have single digit palindrome
				// Because its digit array
				process.stdout.write(" " + digits[0] + 1 + "\n");
			}
			else
			{
				// When array is form of palindrome
				// Define some useful auxiliary variables
				var mid = parseInt(n / 2);
				var carry = 0;
				var left = mid - 1;
				var right = mid + 1;
				if (n % 2 == 0)
				{
					right = mid;
					if (digits[left] <= digits[right])
					{
						// When have need to include carry
						carry = 1;
					}
				}
				else
				{
					digits[mid] += 1;
					// Calculate carry
					carry = parseInt(digits[mid] / 10);
					if (carry != 0)
					{
						// When middle element is overflow
						digits[mid] = 0;
					}
				}
				// Equal the left part to right part, 
				// And include carry when need
				while (left >= 0)
				{
					if (digits[left] == 9 && carry == 1)
					{
						// When central element is 9
						// Set zero
						digits[left] = 0;
						digits[right] = 0;
					}
					else
					{
						// Set left element to right part
						digits[left] = digits[left] + carry;
						digits[right] = digits[left];
						// reset the carry
						carry = 0;
					}
					// Change index location
					left--;
					right++;
				}
				this.printResult(digits, n);
			}
		}
	}
}

function main()
{
	var task = new Palindrome();
	// Define array of positive digits
	var digits1 = [1, 9, 1];
	var digits2 = [1, 2, 3, 4, 1];
	var digits3 = [1, 1, 1, 1, 1, 1, 1, 1];
	var digits4 = [9, 9, 9, 9, 9, 9, 9];
	var digits5 = [2, 0, 7, 8, 2, 2];
	var digits6 = [2, 0, 7, 4, 2, 2];
	// Test A
	var n = digits1.length;
	task.nextPalindrome(digits1, n);
	// Test B
	n = digits2.length;
	task.nextPalindrome(digits2, n);
	// Test C
	n = digits3.length;
	task.nextPalindrome(digits3, n);
	// Test D
	n = digits4.length;
	task.nextPalindrome(digits4, n);
	// Test E
	n = digits5.length;
	task.nextPalindrome(digits5, n);
	// Test G
	n = digits6.length;
	task.nextPalindrome(digits6, n);
}
main();

input

 2 0 2
 1 2 4 2 1
 1 1 1 2 2 1 1 1
 1 0 0 0 0 0 0 1
 2 0 8 8 0 2
 2 0 7 7 0 2
#  Python 3 Program for
#  Find the next smallest palindrome in an array 
class Palindrome :
	#  Display given digits
	def printResult(self, digits, n) :
		i = 0
		while (i < n) :
			print(" ", digits[i], end = "")
			i += 1
		
		print(end = "\n")
	
	#  Handles the request of finding next palindrome
	def nextPalindrome(self, digits, n) :
		i = 0
		#  Check that all 9 present in given list
		while (i < n) :
			if (digits[i] != 9) :
				#  When element is not 9
				i = n + 1
			
			i += 1
		
		if (i == n) :
			i = 0
			#  When have series of 9..99.. 
			#  Display result
			while (i <= n) :
				if (i == 0 or i == n) :
					print("  1", end = "")
				else :
					print("  0", end = "")
				
				i += 1
			
			print(end = "\n")
		else :
			if (n == 1) :
				#  When have single digit palindrome
				#  Because its digit list
				print(" ", digits[0] + 1 )
			else :
				mid = int(n / 2)
				carry = 0
				left = mid - 1
				right = mid + 1
				if (n % 2 == 0) :
					right = mid
					if (digits[left] <= digits[right]) :
						#  When have need to include carry
						carry = 1
					
				else :
					digits[mid] += 1
					#  Calculate carry
					carry = int(digits[mid] / 10)
					if (carry != 0) :
						#  When middle element is overflow
						digits[mid] = 0
					
				
				#  Equal the left part to right part, 
				#  And include carry when need
				while (left >= 0) :
					if (digits[left] == 9 and carry == 1) :
						#  When central element is 9
						#  Set zero
						digits[left] = 0
						digits[right] = 0
					else :
						#  Set left element to right part
						digits[left] = digits[left] + carry
						digits[right] = digits[left]
						#  reset the carry
						carry = 0
					
					#  Change index location
					left -= 1
					right += 1
				
				self.printResult(digits, n)
			
		
	

def main() :
	task = Palindrome()
	digits1 = [1, 9, 1]
	digits2 = [1, 2, 3, 4, 1]
	digits3 = [1, 1, 1, 1, 1, 1, 1, 1]
	digits4 = [9, 9, 9, 9, 9, 9, 9]
	digits5 = [2, 0, 7, 8, 2, 2]
	digits6 = [2, 0, 7, 4, 2, 2]
	n = len(digits1)
	task.nextPalindrome(digits1, n)
	#  Test B
	n = len(digits2)
	task.nextPalindrome(digits2, n)
	#  Test C
	n = len(digits3)
	task.nextPalindrome(digits3, n)
	#  Test D
	n = len(digits4)
	task.nextPalindrome(digits4, n)
	#  Test E
	n = len(digits5)
	task.nextPalindrome(digits5, n)
	#  Test G
	n = len(digits6)
	task.nextPalindrome(digits6, n)

if __name__ == "__main__": main()

input

  2  0  2
  1  2  4  2  1
  1  1  1  2  2  1  1  1
  1  0  0  0  0  0  0  1
  2  0  8  8  0  2
  2  0  7  7  0  2
#  Ruby Program for
#  Find the next smallest palindrome in an array 
class Palindrome 
	#  Display given digits
	def printResult(digits, n) 
		i = 0
		while (i < n) 
			print(" ", digits[i])
			i += 1
		end

		print("\n")
	end

	#  Handles the request of finding next palindrome
	def nextPalindrome(digits, n) 
		i = 0
		#  Check that all 9 present in given array
		i = 0
		while (i < n) 
			if (digits[i] != 9) 
				#  When element is not 9
				i = n + 1
			end

			i += 1
		end

		if (i == n) 
			#  When have series of 9..99.. 
			#  Display result
			i = 0
			while (i <= n) 
				if (i == 0 || i == n) 
					print(" 1")
				else 
					print(" 0")
				end

				i += 1
			end

			print("\n")
		else 
			if (n == 1) 
				#  When have single digit palindrome
				#  Because its digit array
				print(" ", digits[0] + 1 ,"\n")
			else 
				#  When array is form of palindrome
				#  Define some useful auxiliary variables
				mid = n / 2
				carry = 0
				left = mid - 1
				right = mid + 1
				if (n % 2 == 0) 
					right = mid
					if (digits[left] <= digits[right]) 
						#  When have need to include carry
						carry = 1
					end

				else 
					digits[mid] += 1
					#  Calculate carry
					carry = digits[mid] / 10
					if (carry != 0) 
						#  When middle element is overflow
						digits[mid] = 0
					end

				end

				#  Equal the left part to right part, 
				#  And include carry when need
				while (left >= 0) 
					if (digits[left] == 9 && carry == 1) 
						#  When central element is 9
						#  Set zero
						digits[left] = 0
						digits[right] = 0
					else 
						#  Set left element to right part
						digits[left] = digits[left] + carry
						digits[right] = digits[left]
						#  reset the carry
						carry = 0
					end

					#  Change index location
					left -= 1
					right += 1
				end

				self.printResult(digits, n)
			end

		end

	end

end

def main() 
	task = Palindrome.new()
	#  Define array of positive digits
	digits1 = [1, 9, 1]
	digits2 = [1, 2, 3, 4, 1]
	digits3 = [1, 1, 1, 1, 1, 1, 1, 1]
	digits4 = [9, 9, 9, 9, 9, 9, 9]
	digits5 = [2, 0, 7, 8, 2, 2]
	digits6 = [2, 0, 7, 4, 2, 2]
	#  Test A
	n = digits1.length
	task.nextPalindrome(digits1, n)
	#  Test B
	n = digits2.length
	task.nextPalindrome(digits2, n)
	#  Test C
	n = digits3.length
	task.nextPalindrome(digits3, n)
	#  Test D
	n = digits4.length
	task.nextPalindrome(digits4, n)
	#  Test E
	n = digits5.length
	task.nextPalindrome(digits5, n)
	#  Test G
	n = digits6.length
	task.nextPalindrome(digits6, n)
end

main()

input

 2 0 2
 1 2 4 2 1
 1 1 1 2 2 1 1 1
 1 0 0 0 0 0 0 1
 2 0 8 8 0 2
 2 0 7 7 0 2

/*
  Scala Program for
  Find the next smallest palindrome in an array 
*/
class Palindrome()
{
	// Display given digits
	def printResult(digits: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print(" " + digits(i));
			i += 1;
		}
		print("\n");
	}
	// Handles the request of finding next palindrome
	def nextPalindrome(digits: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		// Check that all 9 present in given array
		i = 0;
		while (i < n)
		{
			if (digits(i) != 9)
			{
				// When element is not 9
				i = n + 1;
			}
			i += 1;
		}
		if (i == n)
		{
			// When have series of 9..99.. 
			// Display result
			i = 0;
			while (i <= n)
			{
				if (i == 0 || i == n)
				{
					print(" 1");
				}
				else
				{
					print(" 0");
				}
				i += 1;
			}
			print("\n");
		}
		else
		{
			if (n == 1)
			{
				// When have single digit palindrome
				// Because its digit array
				print(" " + digits(0) + 1 + "\n");
			}
			else
			{
				// When array is form of palindrome
				// Define some useful auxiliary variables
				var mid: Int = (n / 2).toInt;
				var carry: Int = 0;
				var left: Int = mid - 1;
				var right: Int = mid + 1;
				if (n % 2 == 0)
				{
					right = mid;
					if (digits(left) <= digits(right))
					{
						// When have need to include carry
						carry = 1;
					}
				}
				else
				{
					digits(mid) += 1;
					// Calculate carry
					carry = (digits(mid) / 10).toInt;
					if (carry != 0)
					{
						// When middle element is overflow
						digits(mid) = 0;
					}
				}
				// Equal the left part to right part, 
				// And include carry when need
				while (left >= 0)
				{
					if (digits(left) == 9 && carry == 1)
					{
						// When central element is 9
						// Set zero
						digits(left) = 0;
						digits(right) = 0;
					}
					else
					{
						// Set left element to right part
						digits(left) = digits(left) + carry;
						digits(right) = digits(left);
						// reset the carry
						carry = 0;
					}
					// Change index location
					left -= 1;
					right += 1;
				}
				printResult(digits, n);
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Palindrome = new Palindrome();
		// Define array of positive digits
		var digits1: Array[Int] = Array(1, 9, 1);
		var digits2: Array[Int] = Array(1, 2, 3, 4, 1);
		var digits3: Array[Int] = Array(1, 1, 1, 1, 1, 1, 1, 1);
		var digits4: Array[Int] = Array(9, 9, 9, 9, 9, 9, 9);
		var digits5: Array[Int] = Array(2, 0, 7, 8, 2, 2);
		var digits6: Array[Int] = Array(2, 0, 7, 4, 2, 2);
		// Test A
		var n: Int = digits1.length;
		task.nextPalindrome(digits1, n);
		// Test B
		n = digits2.length;
		task.nextPalindrome(digits2, n);
		// Test C
		n = digits3.length;
		task.nextPalindrome(digits3, n);
		// Test D
		n = digits4.length;
		task.nextPalindrome(digits4, n);
		// Test E
		n = digits5.length;
		task.nextPalindrome(digits5, n);
		// Test G
		n = digits6.length;
		task.nextPalindrome(digits6, n);
	}
}

input

 2 0 2
 1 2 4 2 1
 1 1 1 2 2 1 1 1
 1 0 0 0 0 0 0 1
 2 0 8 8 0 2
 2 0 7 7 0 2
/*
  Swift 4 Program for
  Find the next smallest palindrome in an array 
*/
class Palindrome
{
	// Display given digits
	func printResult(_ digits: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" ", digits[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	// Handles the request of finding next palindrome
	func nextPalindrome(_ digits: inout [Int], _ n: Int)
	{
		var i: Int = 0;
		// Check that all 9 present in given array
		i = 0;
		while (i < n)
		{
			if (digits[i]  != 9)
			{
				// When element is not 9
				i = n + 1;
			}
			i += 1;
		}
		if (i == n)
		{
			// When have series of 9..99.. 
			// Display result
			i = 0;
			while (i <= n)
			{
				if (i == 0 || i == n)
				{
					print("  1", terminator: "");
				}
				else
				{
					print("  0", terminator: "");
				}
				i += 1;
			}
			print(terminator: "\n");
		}
		else
		{
			if (n == 1)
			{
				// When have single digit palindrome
				// Because its digit array
				print(" ", digits[0] + 1 );
			}
			else
			{
				// When array is form of palindrome
				// Define some useful auxiliary variables
				let mid: Int = n / 2;
				var carry: Int = 0;
				var left: Int = mid - 1;
				var right: Int = mid + 1;
				if (n % 2 == 0)
				{
					right = mid;
					if (digits[left] <= digits[right])
					{
						// When have need to include carry
						carry = 1;
					}
				}
				else
				{
					digits[mid] += 1;
					// Calculate carry
					carry = digits[mid] / 10;
					if (carry  != 0)
					{
						// When middle element is overflow
						digits[mid] = 0;
					}
				}
				// Equal the left part to right part, 
				// And include carry when need
				while (left >= 0)
				{
					if (digits[left] == 9 && carry == 1)
					{
						// When central element is 9
						// Set zero
						digits[left] = 0;
						digits[right] = 0;
					}
					else
					{
						// Set left element to right part
						digits[left] = digits[left] + carry;
						digits[right] = digits[left];
						// reset the carry
						carry = 0;
					}
					// Change index location
					left -= 1;
					right += 1;
				}
				self.printResult(digits, n);
			}
		}
	}
}
func main()
{
	let task: Palindrome = Palindrome();
	// Define array of positive digits
	var digits1: [Int] = [1, 9, 1];
	var digits2: [Int] = [1, 2, 3, 4, 1];
	var digits3: [Int] = [1, 1, 1, 1, 1, 1, 1, 1];
	var digits4: [Int] = [9, 9, 9, 9, 9, 9, 9];
	var digits5: [Int] = [2, 0, 7, 8, 2, 2];
	var digits6: [Int] = [2, 0, 7, 4, 2, 2];
	// Test A
	var n: Int = digits1.count;
	task.nextPalindrome(&digits1, n);
	// Test B
	n = digits2.count;
	task.nextPalindrome(&digits2, n);
	// Test C
	n = digits3.count;
	task.nextPalindrome(&digits3, n);
	// Test D
	n = digits4.count;
	task.nextPalindrome(&digits4, n);
	// Test E
	n = digits5.count;
	task.nextPalindrome(&digits5, n);
	// Test G
	n = digits6.count;
	task.nextPalindrome(&digits6, n);
}
main();

input

  2  0  2
  1  2  4  2  1
  1  1  1  2  2  1  1  1
  1  0  0  0  0  0  0  1
  2  0  8  8  0  2
  2  0  7  7  0  2
/*
  Kotlin Program for
  Find the next smallest palindrome in an array 
*/
class Palindrome
{
	// Display given digits
	fun printResult(digits: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" " + digits[i]);
			i += 1;
		}
		print("\n");
	}
	// Handles the request of finding next palindrome
	fun nextPalindrome(digits: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;

		while (i < n)
		{
			if (digits[i] != 9)
			{
				// When element is not 9
				i = n + 1;
			}
			i += 1;
		}
		if (i == n)
		{
			i = 0;
			while (i <= n)
			{
				if (i == 0 || i == n)
				{
					print(" 1");
				}
				else
				{
					print(" 0");
				}
				i += 1;
			}
			print("\n");
		}
		else
		{
			if (n == 1)
			{
				// When have single digit palindrome
				// Because its digit array
				print(" " + digits[0] + 1 + "\n");
			}
			else
			{
				// When array is form of palindrome
				// Define some useful auxiliary variables
				val mid: Int = n / 2;
				var carry: Int = 0;
				var left: Int = mid - 1;
				var right: Int = mid + 1;
				if (n % 2 == 0)
				{
					right = mid;
					if (digits[left] <= digits[right])
					{
						// When have need to include carry
						carry = 1;
					}
				}
				else
				{
					digits[mid] += 1;
					// Calculate carry
					carry = digits[mid] / 10;
					if (carry != 0)
					{
						// When middle element is overflow
						digits[mid] = 0;
					}
				}
				while (left >= 0)
				{
					if (digits[left] == 9 && carry == 1)
					{
						// When central element is 9
						// Set zero
						digits[left] = 0;
						digits[right] = 0;
					}
					else
					{
						// Set left element to right part
						digits[left] = digits[left] + carry;
						digits[right] = digits[left];
						// reset the carry
						carry = 0;
					}
					// Change index location
					left -= 1;
					right += 1;
				}
				this.printResult(digits, n);
			}
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Palindrome = Palindrome();
	// Define array of positive digits
	var digits1: Array < Int > = arrayOf(1, 9, 1);
	var digits2: Array < Int > = arrayOf(1, 2, 3, 4, 1);
	var digits3: Array < Int > = arrayOf(1, 1, 1, 1, 1, 1, 1, 1);
	var digits4: Array < Int > = arrayOf(9, 9, 9, 9, 9, 9, 9);
	var digits5: Array < Int > = arrayOf(2, 0, 7, 8, 2, 2);
	var digits6: Array < Int > = arrayOf(2, 0, 7, 4, 2, 2);
	// Test A
	var n: Int = digits1.count();
	task.nextPalindrome(digits1, n);
	// Test B
	n = digits2.count();
	task.nextPalindrome(digits2, n);
	// Test C
	n = digits3.count();
	task.nextPalindrome(digits3, n);
	// Test D
	n = digits4.count();
	task.nextPalindrome(digits4, n);
	// Test E
	n = digits5.count();
	task.nextPalindrome(digits5, n);
	// Test G
	n = digits6.count();
	task.nextPalindrome(digits6, n);
}

input

 2 0 2
 1 2 4 2 1
 1 1 1 2 2 1 1 1
 1 0 0 0 0 0 0 1
 2 0 8 8 0 2
 2 0 7 7 0 2

Time Complexity

The time complexity of the algorithm mainly depends on the length of the input array n. The key steps include checking for all 9's, incrementing a single-digit number, and adjusting digits to create the palindrome. All of these steps take linear time with respect to the length of the array. Therefore, the overall time complexity of the algorithm is O(n).

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment





Categories
Relative Post