Given a number, in the form of an array num[] of size n containing digits from 1 to 9(inclusive). Find the next smallest palindrome strictly larger than the given number.
Input: num[] = [9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2]
Output: [9, 4, 1, 8, 8, 0, 8, 8, 1, 4, 9]
Explanation: Next smallest palindrome is 9 4 1 8 8 0 8 8 1 4 9Input: num[] = [2, 3, 5, 4, 5]
Output: [2, 3, 6, 3, 2]
Explanation: Next smallest palindrome is 2 3 6 3 2
Try it on GfG Practice
Table of Content
Try All Possible Numbers
The idea is to keep adding 1 to the number and check if it becomes a palindrome. Stop when a palindrome is found.
#include <iostream>
#include <vector>
using namespace std;
int checkPalindrome(vector<int>& num) {
int n = num.size();
for (int i = 0; i < n / 2; ++i) {
if (num[i] != num[n - 1 - i]) {
return 0;
}
}
return 1;
}
vector<int> nextPalindrome(vector<int>& num) {
int n = num.size();
while (true) {
// Add 1 to the number (always do this first)
int carry = 1;
for (int i = n - 1; i >= 0; --i) {
num[i] += carry;
if (num[i] == 10) {
num[i] = 0;
carry = 1;
} else {
carry = 0;
break;
}
}
// If carry remains, insert 1 at beginning
if (carry == 1) {
num.insert(num.begin(), 1);
n++;
}
// Check if palindrome
if (checkPalindrome(num)) {
break;
}
}
return num;
}
int main() {
vector<int> num = {9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2};
vector<int> res = nextPalindrome(num);
for (int i = 0; i < res.size(); ++i) {
cout << res[i] << " ";
}
cout << endl;
return 0;
}
import java.util.*;
class GFG {
static int checkPalindrome(List<Integer> num) {
int n = num.size();
for (int i = 0; i < n / 2; i++) {
if (!num.get(i).equals(num.get(n - 1 - i))) {
return 0;
}
}
return 1;
}
static List<Integer> nextPalindrome(List<Integer> num) {
int n = num.size();
while (true) {
// Add 1 to the number (always do this first)
int carry = 1;
for (int i = n - 1; i >= 0; i--) {
num.set(i, num.get(i) + carry);
if (num.get(i) == 10) {
num.set(i, 0);
carry = 1;
} else {
carry = 0;
break;
}
}
// If carry remains, insert 1 at beginning
if (carry == 1) {
num.add(0, 1);
n++;
}
// Check if palindrome
if (checkPalindrome(num) == 1) {
break;
}
}
return num;
}
public static void main(String[] args) {
List<Integer> num = new ArrayList<>(Arrays.asList(
9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2
));
List<Integer> res = nextPalindrome(num);
for (int x : res) {
System.out.print(x + " ");
}
}
}
def checkPalindrome(num):
n = len(num)
for i in range(n // 2):
if num[i] != num[n - 1 - i]:
return 0
return 1
def nextPalindrome(num):
n = len(num)
while True:
# Add 1 to the number (always do this first)
carry = 1
for i in range(n - 1, -1, -1):
num[i] += carry
if num[i] == 10:
num[i] = 0
carry = 1
else:
carry = 0
break
# If carry remains, insert 1 at beginning
if carry == 1:
num.insert(0, 1)
n += 1
# Check if palindrome
if checkPalindrome(num):
break
return num
if __name__ == "__main__":
num = [9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2]
res = nextPalindrome(num)
print(*res)
using System;
using System.Collections.Generic;
class GFG {
static int checkPalindrome(List<int> num) {
int n = num.Count;
for (int i = 0; i < n / 2; i++) {
if (num[i] != num[n - 1 - i]) {
return 0;
}
}
return 1;
}
static List<int> nextPalindrome(List<int> num) {
int n = num.Count;
while (true) {
// Add 1 to the number (always do this first)
int carry = 1;
for (int i = n - 1; i >= 0; i--) {
num[i] += carry;
if (num[i] == 10) {
num[i] = 0;
carry = 1;
} else {
carry = 0;
break;
}
}
// If carry remains, insert 1 at beginning
if (carry == 1) {
num.Insert(0, 1);
n++;
}
// Check if palindrome
if (checkPalindrome(num) == 1) {
break;
}
}
return num;
}
static void Main() {
List<int> num = new List<int> { 9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2 };
List<int> res = nextPalindrome(num);
foreach (int x in res) {
Console.Write(x + " ");
}
}
}
function checkPalindrome(num) {
let n = num.length;
for (let i = 0; i < Math.floor(n / 2); i++) {
if (num[i] !== num[n - 1 - i]) {
return 0;
}
}
return 1;
}
function nextPalindrome(num) {
let n = num.length;
while (true) {
// Add 1 to the number (always do this first)
let carry = 1;
for (let i = n - 1; i >= 0; i--) {
num[i] += carry;
if (num[i] === 10) {
num[i] = 0;
carry = 1;
} else {
carry = 0;
break;
}
}
// If carry remains, insert 1 at beginning
if (carry === 1) {
num.unshift(1);
n++;
}
// Check if palindrome
if (checkPalindrome(num)) {
break;
}
}
return num;
}
// Driver code
let num = [9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2];
let res = nextPalindrome(num);
console.log(res.join(" "));
Output
9 4 1 8 8 0 8 8 1 4 9
Time Complexity: Worst case O(n × 10ⁿ) because many numbers may be generated before finding the next palindrome, and each palindrome check takes O(n) time.
Space Complexity: The space complexity is O(n), since the number is stored and processed as an array of digits.
Using Mirror and Carry Propagation - O(n) time and O(n) space
- If all digits are 9, return 1 followed by zeros and ending with 1 (Example: 999 → 1001).
- Otherwise, Copy the left half to the right to form a palindrome.
- If it is not greater than the original, increase the middle digit (odd length) or middle pair (even length).
- If a carry occurs, propagate it to the left and mirror the left half again to get the next palindrome.
#include <iostream>
#include <vector>
using namespace std;
//to check if all digits in num[] are 9
int AreAll9s(const vector<int>& num) {
for (int i = 0; i < num.size(); ++i) {
if (num[i] != 9) return 0;
}
return 1;
}
// generate the next palindrome
void nextPalindromeUtil(vector<int>& num) {
int n = num.size();
int mid = n / 2;
bool leftSmaller = false;
int i = mid - 1;
int j = (n % 2) ? mid + 1 : mid;
// Compare the left side with the right side
while (i >= 0 && num[i] == num[j]) i--, j++;
// Check if we need to increment the middle digit(s)
if (i < 0 || num[i] < num[j]) leftSmaller = true;
// Copy the left half to the right half
while (i >= 0) {
num[j] = num[i];
j++;
i--;
}
// If middle digits need to be incremented
if (leftSmaller) {
int carry = 1;
i = mid - 1;
if (n % 2 == 1) {
num[mid] += carry;
carry = num[mid] / 10;
num[mid] %= 10;
j = mid + 1;
} else {
j = mid;
}
while (i >= 0) {
num[i] += carry;
carry = num[i] / 10;
num[i] %= 10;
num[j++] = num[i--];
}
}
}
vector<int> nextPalindrome(vector<int>& num) {
vector<int> ans;
if (AreAll9s(num)) {
ans.push_back(1);
for (int i = 1; i < num.size(); i++) ans.push_back(0);
ans.push_back(1);
} else {
nextPalindromeUtil(num);
for (int i = 0; i < num.size(); i++) {
ans.push_back(num[i]);
}
}
return ans;
}
int main() {
vector<int> num = {9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2};
vector<int> result = nextPalindrome(num);
for (int i : result) {
cout << i << " ";
}
cout << endl;
return 0;
}
import java.util.ArrayList;
import java.util.Arrays;
// to check if all digits in num[] are 9
class NextPalindrome {
static boolean areAll9s(int[] num) {
for (int d : num) {
if (d != 9) return false;
}
return true;
}
// generate the next palindrome
static void nextPalindromeUtil(int[] num) {
int n = num.length;
int mid = n / 2;
boolean leftSmaller = false;
int i = mid - 1;
int j = (n % 2 == 1) ? mid + 1 : mid;
// Compare the left side with the right side
while (i >= 0 && num[i] == num[j]) {
i--;
j++;
}
// Check if we need to increment the middle digit(s)
if (i < 0 || num[i] < num[j]) leftSmaller = true;
// Copy the left half to the right half
while (i >= 0) {
num[j++] = num[i--];
}
// If middle digits need to be incremented
if (leftSmaller) {
int carry = 1;
i = mid - 1;
if (n % 2 == 1) {
num[mid] += carry;
carry = num[mid] / 10;
num[mid] %= 10;
j = mid + 1;
} else {
j = mid;
}
while (i >= 0) {
num[i] += carry;
carry = num[i] / 10;
num[i] %= 10;
num[j++] = num[i--];
}
}
}
static ArrayList<Integer> nextPalindrome(int[] num) {
ArrayList<Integer> ans = new ArrayList<>();
if (areAll9s(num)) {
ans.add(1);
for (int i = 1; i < num.length; i++) ans.add(0);
ans.add(1);
return ans;
}
nextPalindromeUtil(num);
for (int d : num) ans.add(d);
return ans;
}
public static void main(String[] args) {
int[] num = {9,4,1,8,7,9,7,8,3,2,2};
ArrayList<Integer> res = nextPalindrome(num);
System.out.println(res);
}
}
# check if all digits in num[] are 9
def are_all_9s(num):
for d in num:
if d != 9:
return False
return True
# generate the next palindrome
def next_palindrome_util(num):
n = len(num)
mid = n // 2
left_smaller = False
i = mid - 1
j = mid + 1 if n % 2 else mid
# Compare the left side with the right side
while i >= 0 and num[i] == num[j]:
i -= 1
j += 1
# Check if we need to increment the middle digit(s)
if i < 0 or num[i] < num[j]:
left_smaller = True
# Copy the left half to the right half
while i >= 0:
num[j] = num[i]
i -= 1
j += 1
# If middle digits need to be incremented
if left_smaller:
carry = 1
i = mid - 1
if n % 2:
num[mid] += carry
carry = num[mid] // 10
num[mid] %= 10
j = mid + 1
else:
j = mid
while i >= 0:
num[i] += carry
carry = num[i] // 10
num[i] %= 10
num[j] = num[i]
i -= 1
j += 1
def next_palindrome(num):
if are_all_9s(num):
return [1] + [0] * (len(num) - 1) + [1]
next_palindrome_util(num)
return num
if __name__=="__main__":
num = [9,4,1,8,7,9,7,8,3,2,2]
print(next_palindrome(num))
using System;
using System.Collections.Generic;
//check if all digits in num[] are 9
class GfG
{
static bool AreAll9s(List<int> num)
{
foreach (int d in num)
if (d != 9) return false;
return true;
}
// generate the next palindrome
static void NextPalindromeUtil(List<int> num)
{
int n = num.Count;
int mid = n / 2;
bool leftSmaller = false;
int i = mid - 1;
int j = (n % 2 == 1) ? mid + 1 : mid;
// Compare the left side with the right side
while (i >= 0 && num[i] == num[j])
{
i--;
j++;
}
// Check if we need to increment the middle digit(s)
if (i < 0 || num[i] < num[j]) leftSmaller = true;
// Copy the left half to the right half
while (i >= 0)
{
num[j++] = num[i--];
}
// If middle digits need to be incremented
if (leftSmaller)
{
int carry = 1;
i = mid - 1;
if (n % 2 == 1)
{
num[mid] += carry;
carry = num[mid] / 10;
num[mid] %= 10;
j = mid + 1;
}
else j = mid;
while (i >= 0)
{
num[i] += carry;
carry = num[i] / 10;
num[i] %= 10;
num[j++] = num[i--];
}
}
}
static List<int> NextPalindromeFunc(List<int> num)
{
if (AreAll9s(num))
{
var ans = new List<int> {1};
for (int i = 1; i < num.Count; i++) ans.Add(0);
ans.Add(1);
return ans;
}
NextPalindromeUtil(num);
return num;
}
static void Main()
{
var num = new List<int> {9,4,1,8,7,9,7,8,3,2,2};
Console.WriteLine(string.Join(" ", NextPalindromeFunc(num)));
}
}
// to check if all digits in num[] are 9
function areAll9s(num) {
for (let d of num) {
if (d !== 9) return false;
}
return true;
}
// generate the next palindrome
function nextPalindromeUtil(num) {
const n = num.length;
const mid = Math.floor(n / 2);
let leftSmaller = false;
let i = mid - 1;
let j = (n % 2 === 1) ? mid + 1 : mid;
// Compare the left side with the right side
while (i >= 0 && num[i] === num[j]) {
i--;
j++;
}
// Check if we need to increment the middle digit(s)
if (i < 0 || num[i] < num[j]) leftSmaller = true;
// Copy the left half to the right half
while (i >= 0) {
num[j++] = num[i--];
}
// If middle digits need to be incremented
if (leftSmaller) {
let carry = 1;
i = mid - 1;
if (n % 2 === 1) {
num[mid] += carry;
carry = Math.floor(num[mid] / 10);
num[mid] %= 10;
j = mid + 1;
} else {
j = mid;
}
while (i >= 0) {
num[i] += carry;
carry = Math.floor(num[i] / 10);
num[i] %= 10;
num[j++] = num[i--];
}
}
}
function nextPalindrome(num) {
if (areAll9s(num)) {
return [1, ...Array(num.length - 1).fill(0), 1];
}
nextPalindromeUtil(num);
return num;
}
// Driver code
const num = [9,4,1,8,7,9,7,8,3,2,2];
console.log(nextPalindrome(num).join(" "));
Output
9 4 1 8 8 0 8 8 1 4 9