Given an integer N, the task is to find the closest number to N which is greater than N and contains at most one non-zero digit.
Examples:
Input: N = 540
Output: 600
Explanation: Since the number 600 contains only one non-zero digit, it is the required output is 600.Input: N = 1000
Output: 2000
Approach: The problem can be solved based on the following observations.
Follow the steps below to solve the problem:
- Initialize a variable, say, ctr to store the count of digits in N.
- Compute the value of power(10, ctr – 1)
- Print the value of the above-mentioned formula as the required answer.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate// X ^ n in log(n)int power(int X, int n) { // Stores the value // of X^n int res = 1; while(n) { // If N is odd if(n & 1) res = res * X; X = X * X; n = n >> 1; } return res; }// Function to find the// closest number > N having // at most 1 non-zero digitint closestgtNum(int N) { // Stores the count // of digits in N int n = log10(N) + 1; // Stores the power // of 10^(n-1) int P = power(10, n - 1); // Stores the // last (n - 1) digits int Y = N % P; // Store the answer int res = N + (P - Y); return res;}// Driver Codeint main(){ int N = 120; cout<<closestgtNum(N);} |
Java
// Java program to implement // the above approach import java.io.*;class GFG{ // Function to calculate// X ^ n in log(n)static int power(int X, int n) { // Stores the value // of X^n int res = 1; while(n != 0) { // If N is odd if ((n & 1) != 0) res = res * X; X = X * X; n = n >> 1; } return res;} // Function to find the// closest number > N having // at most 1 non-zero digitstatic int closestgtNum(int N){ // Stores the count // of digits in N int n = (int) Math.log10(N) + 1; // Stores the power // of 10^(n-1) int P = power(10, n - 1); // Stores the // last (n - 1) digits int Y = N % P; // Store the answer int res = N + (P - Y); return res;} // Driver Codepublic static void main (String[] args) { int N = 120; // Function call System.out.print(closestgtNum(N));}}// This code is contributed by code_hunt |
Python3
# Python3 program to implement # the above approach import math# Function to calculate# X ^ n in log(n)def power(X, n): # Stores the value # of X^n res = 1 while (n != 0): # If N is odd if (n & 1 != 0): res = res * X X = X * X n = n >> 1 return res # Function to find the# closest number > N having # at most 1 non-zero digitdef closestgtNum(N): # Stores the count # of digits in N n = int(math.log10(N) + 1) # Stores the power # of 10^(n-1) P = power(10, n - 1) # Stores the # last (n - 1) digits Y = N % P # Store the answer res = N + (P - Y) return res# Driver CodeN = 120print(closestgtNum(N))# This code is contributed by code_hunt |
C#
// C# program to implement // the above approach using System;class GFG{ // Function to calculate// X ^ n in log(n)static int power(int X, int n){ // Stores the value // of X^n int res = 1; while(n != 0) { // If N is odd if ((n & 1) != 0) res = res * X; X = X * X; n = n >> 1; } return res;} // Function to find the// closest number > N having // at most 1 non-zero digitstatic int closestgtNum(int N) { // Stores the count // of digits in N int n = (int) Math.Log10(N) + 1; // Stores the power // of 10^(n-1) int P = power(10, n - 1); // Stores the // last (n - 1) digits int Y = N % P; // Store the answer int res = N + (P - Y); return res;} // Driver Codepublic static void Main () { int N = 120; // Function call Console.Write(closestgtNum(N));}}// This code is contributed by code_hunt |
Javascript
<script>// JavaScript program to implement // the above approach // Function to calculate// X ^ n in log(n)function power(X, n){ // Stores the value // of X^n var res = 1; while(n != 0) { // If N is odd if ((n & 1) != 0) res = res * X; X = X * X; n = n >> 1; } return res;} // Function to find the// closest number > N having // at most 1 non-zero digitfunction closestgtNum(N) { // Stores the count // of digits in N var n = parseInt( Math.log10(N) + 1); // Stores the power // of 10^(n-1) var P = power(10, n - 1); // Stores the // last (n - 1) digits var Y = N % P; // Store the answer var res = N + (P - Y); return res;} // Driver Codevar N = 120;// Function calldocument.write(closestgtNum(N));</script> |
Output
200
Time Complexity: O(log2N)
Auxiliary Space: O(log10N)
Efficient Approach:The idea is to increment the value of the first digit of the given integer by 1 and initialize the resultant string to the first digit of the given integer. Finally, append (N – 1) 0s at the end of the resultant string and return the resultant string.
- Initialize a string, say res to store the closest greater number with st most one non-zero digit.
- First append the value str[0] + 1 at the resultant string and then append (N – 1) 0s at the end of resultant string.
- Print the value of res
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to get closest greater// number with at most non zero digitstring closestgtNum(string str){ // Stores the closest greater number // with at most one non-zero digit string res = ""; // Stores length of str int n = str.length(); if(str[0] < '9') { res.push_back(str[0] + 1); } else{ // Append 10 to the end // of resultant string res.push_back('1'); res.push_back('0'); } // Append n-1 times '0' to the end // of resultant string for(int i = 0; i < n - 1; i++) { res.push_back('0'); } return res; }// Driver Codeint main(){ string str = "120"; cout<<closestgtNum(str);} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Function to get closest greater// number with at most non zero digitstatic String closestgtNum(String str){ // Stores the closest greater number // with at most one non-zero digit String res = ""; // Stores length of str int n = str.length(); if (str.charAt(0) < '9') { res += (char)(str.charAt(0) + 1); } else { // Append 10 to the end // of resultant String res += (char)('1'); res += (char)('0'); } // Append n-1 times '0' to the end // of resultant String for(int i = 0; i < n - 1; i++) { res += (char)('0'); } return res;}// Driver Codepublic static void main(String[] args){ String str = "120"; System.out.print(closestgtNum(str));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to implement# the above approach# Function to get closest greater# number with at most non zero digitdef closestgtNum(str): # Stores the closest greater number # with at most one non-zero digit res = ""; # Stores length of str n = len(str); if (str[0] < '9'): res += (chr)(ord(str[0]) + 1); else: # Append 10 to the end # of resultant String res += (chr)('1'); res += (chr)('0'); # Append n-1 times '0' to the end # of resultant String for i in range(n - 1): res += ('0'); return res;# Driver Codeif __name__ == '__main__': str = "120"; print(closestgtNum(str));# This code is contributed by Amit Katiyar |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to get closest greater// number with at most non zero digitpublic static string closestgtNum(string str){ // Stores the closest greater number // with at most one non-zero digit string res = ""; // Stores length of str int n = str.Length; if (str[0] < '9') { res = res + (char)(str[0] + 1); } else { // Append 10 to the end // of resultant string res = res + '1'; res = res + '0'; } // Append n-1 times '0' to the end // of resultant string for(int i = 0; i < n - 1; i++) { res = res + '0'; } return res;}// Driver codestatic void Main() { string str = "120"; Console.WriteLine(closestgtNum(str));}}// This code is contributed by divyeshrabadiya07 |
Javascript
<script> // Javascript program to implement// the above approach // Function to get closest greater// number with at most non zero digitfunction closestgtNum(str){ // Stores the closest greater number // with at most one non-zero digit var res = ""; // Stores length of str var n = str.length; if (str[0] < '9') { res = res + String.fromCharCode(str[0].charCodeAt(0) + 1); } else { // Append 10 to the end // of resultant string res = res + '1'; res = res + '0'; } // Append n-1 times '0' to the end // of resultant string for(var i = 0; i < n - 1; i++) { res = res + '0'; } return res;}// Driver codevar str = "120";document.write(closestgtNum(str));// This code is contributed by itsok.</script> |
Output
200
Time Complexity: O(log10N)
Auxiliary Space: O(log10N)
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!
