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:
- 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 all0
's and a trailing1
. For example, if the input is all9
's, the output will be100...001
. - If the input array contains only a single digit, increment it by
1
and return the result. For example, if the input is9
, the output will be10
. - If the input array is already a palindrome, then we need to adjust the middle digits and propagate any carry to the adjacent digits.
- 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
- We start by checking if all elements in the array are
9
. If yes, we print the result as a palindrome consisting of1
followed by(n-1)
zeros followed by another1
. - If
n
is1
, we increment the single digit by1
and print the result. - If the array is not all
9
's and not of length1
, 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
andright
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
to1
. - 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 to0
. - We iterate through the left half of the array, adjusting digits based on the carry and mirroring the changes to the right half.
- We initialize a variable
- 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).
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