Given an integer N, the task is to find the smallest number to be subtracted from N to obtain a palindrome.
Examples:
Input: N = 1000
Output: 1
Explanation: Since 1000 – 1 = 999, which is a palindrome, the smallest number to be subtracted is 1.Input: N = 3456
Output: 13
Explanation: Since 3456 – 13 = 3443, which is a palindrome, the smallest number to be subtracted is 13.
Approach: Follow the steps below to solve the problem:
- Iterate from N to 0.
- Initialize a counter. At each iteration reverse the reduced value of N and compare it to the current value of N. If both are equal, print the value of the counter.
- Otherwise, increment the counter and continue the loop until N is 0.
- Print the value of the counter.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to evaluate minimum// subtraction required to make// a number palindromevoid minSub(int N){ // Counts number of // subtractions required int count = 0; // Run a loop till N>=0 while (N >= 0) { // Store the current number int num = N; // Store reverse of current number int rev = 0; // Reverse the number while (num != 0) { int digit = num % 10; rev = (rev * 10) + digit; num = num / 10; } // Check if N is palindrome if (N == rev) { break; } // Increment the counter count++; // Reduce the number by 1 N--; } // Print the result cout << count;}// Driver Codeint main(){ int N = 3456; // Function call minSub(N); return 0;} |
Java
// Java program for the// above approachimport java.util.*;class GFG{// Function to evaluate minimum// subtraction required to make// a number palindromestatic void minSub(int N){ // Counts number of // subtractions required int count = 0; // Run a loop till N>=0 while (N >= 0) { // Store the current // number int num = N; // Store reverse of // current number int rev = 0; // Reverse the number while (num != 0) { int digit = num % 10; rev = (rev * 10) + digit; num = num / 10; } // Check if N is // palindrome if (N == rev) { break; } // Increment the counter count++; // Reduce the number // by 1 N--; } // Print the result System.out.print(count);}// Driver Codepublic static void main(String[] args){ int N = 3456; // Function call minSub(N);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function to evaluate minimum# subtraction required to make# a number palindromedef minSub(N): # Counts number of # subtractions required count = 0 # Run a loop till N>=0 while (N >= 0): # Store the current number num = N # Store reverse of current number rev = 0 # Reverse the number while (num != 0): digit = num % 10 rev = (rev * 10) + digit num = num // 10 # Check if N is palindrome if (N == rev): break # Increment the counter count += 1 # Reduce the number by 1 N -= 1 # Print the result print(count)# Driver Codeif __name__ == '__main__': N = 3456 # Function call minSub(N)# This code is contributed by bgangwar59 |
C#
// C# program for the// above approachusing System;class GFG{// Function to evaluate minimum// subtraction required to make// a number palindromestatic void minSub(int N){ // Counts number of // subtractions required int count = 0; // Run a loop till N>=0 while (N >= 0) { // Store the current // number int num = N; // Store reverse of // current number int rev = 0; // Reverse the number while (num != 0) { int digit = num % 10; rev = (rev * 10) + digit; num = num / 10; } // Check if N is // palindrome if (N == rev) { break; } // Increment the counter count++; // Reduce the number // by 1 N--; } // Print the result Console.Write(count);}// Driver Codepublic static void Main(String[] args){ int N = 3456; // Function call minSub(N);}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program for the// above approach// Function to evaluate minimum// subtraction required to make// a number palindromefunction minSub(N){ // Counts number of // subtractions required let count = 0; // Run a loop till N>=0 while (N >= 0) { // Store the current // number let num = N; // Store reverse of // current number let rev = 0; // Reverse the number while (num != 0) { let digit = num % 10; rev = (rev * 10) + digit; num = Math.floor(num / 10); } // Check if N is // palindrome if (N == rev) { break; } // Increment the counter count++; // Reduce the number // by 1 N--; } // Print the result document.write(count);}// Driver Codelet N = 3456;// Function callminSub(N);// This code is contributed by souravghosh0416</script> |
Output:
13
Time Complexity: O(N * K), Where K is the number of digits of the integer.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!