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)
{
// 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;
// Test B
n = digits2.length;
// Test C
n = digits3.length;
// Test D
n = digits4.length;
// Test E
n = digits5.length;
// Test G
n = digits6.length;
}
}``````

#### 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()
{
// 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]);
// Test B
n = sizeof(digits2) / sizeof(digits2[0]);
// Test C
n = sizeof(digits3) / sizeof(digits3[0]);
// Test D
n = sizeof(digits4) / sizeof(digits4[0]);
// Test E
n = sizeof(digits5) / sizeof(digits5[0]);
// Test G
n = sizeof(digits6) / sizeof(digits6[0]);
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)
{
// 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;
// Test B
n = digits2.Length;
// Test C
n = digits3.Length;
// Test D
n = digits4.Length;
// Test E
n = digits5.Length;
// Test G
n = digits6.Length;
}
}``````

#### 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()
{
// 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);
// Test B
\$n = count(\$digits2);
// Test C
\$n = count(\$digits3);
// Test D
\$n = count(\$digits4);
// Test E
\$n = count(\$digits5);
// Test G
\$n = count(\$digits6);
}
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()
{
// 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;
// Test B
n = digits2.length;
// Test C
n = digits3.length;
// Test D
n = digits4.length;
// Test E
n = digits5.length;
// Test G
n = digits6.length;
}
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() :
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)
#  Test B
n = len(digits2)
#  Test C
n = len(digits3)
#  Test D
n = len(digits4)
#  Test E
n = len(digits5)
#  Test G
n = len(digits6)

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()
#  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
#  Test B
n = digits2.length
#  Test C
n = digits3.length
#  Test D
n = digits4.length
#  Test E
n = digits5.length
#  Test G
n = digits6.length
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;
// Test B
n = digits2.length;
// Test C
n = digits3.length;
// Test D
n = digits4.length;
// Test E
n = digits5.length;
// Test G
n = digits6.length;
}
}``````

#### 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()
{
// 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;
// Test B
n = digits2.count;
// Test C
n = digits3.count;
// Test D
n = digits4.count;
// Test E
n = digits5.count;
// Test G
n = digits6.count;
}
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
{
// 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();
// Test B
n = digits2.count();
// Test C
n = digits3.count();
// Test D
n = digits4.count();
// Test E
n = digits5.count();
// Test G
n = digits6.count();
}``````

#### 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.

Categories
Relative Post