Given a number N, we need to write a program to find the smallest number not less than N, which has all digits even.
Examples:
Input: N = 1345
Output: 2000
Explanation: 2000 is the smallest number not less than N, whose all digits are even.Input : N = 2397
Output : 2400
Explanation: 2400 is the smallest number not less than N, whose all digits are even.
Naive approach: A naive approach is to keep iterating from N until we find a number with all digits even.
Below is the implementation of above approach:
C++
// CPP program to print the smallest// integer not less than N with all even digits#include <bits/stdc++.h>using namespace std;// function to check if all digits// are even of a given numberint check_digits(int n){ // iterate for all digits while (n) { if ((n % 10) % 2) // if digit is odd return 0; n /= 10; } // all digits are even return 1;}// function to return the smallest number// with all digits evenint smallest_number(int n){ // iterate till we find a // number with all digits even for (int i = n;; i++) if (check_digits(i)) return i;}// Driver Codeint main(){ int N = 2397; cout << smallest_number(N); return 0;} |
Java
// Java program to print the smallest// integer not less than N with all // even digitsimport java.io.*;public class GFG { // function to check if all digits // are even of a given number static int check_digits(int n) { // iterate for all digits while (n != 0) { // if digit is odd if ((n % 10) % 2 != 0) return 0; n /= 10; } // all digits are even return 1; } // function to return the smallest // number with all digits even static int smallest_number(int n) { // iterate till we find a // number with all digits even for (int i = n; ; i++) if (check_digits(i) != 0) return i; } // Driver Code public static void main(String[] args) { int N = 2397; System.out.println(smallest_number(N)); }}// This code is contributed by// Smitha Dinesh Semwal |
Python3
# Python3 program to print the smallest# integer not less than N with # all even digits# function to check if all digits# are even of a given numberdef check_digits(n) : # iterate for all digits while (n) : # if digit is odd if ((n % 10) % 2) : return 0 n = int(n / 10) # all digits are even return 1# function to return the# smallest number with # all digits evendef smallest_number(n) : # iterate till we find a # number with all digits even for i in range(n, 2401) : if (check_digits(i) == 1) : return (i)# Driver CodeN = 2397print (str(smallest_number(N)))# This code is contributed by # Manish Shaw (manishshaw1) |
C#
// C# program to print the smallest// integer not less than N with all // even digitsusing System;class GFG { // function to check if all digits // are even of a given number static int check_digits(int n) { // iterate for all digits while (n != 0) { // if digit is odd if ((n % 10) % 2 != 0) return 0; n /= 10; } // all digits are even return 1; } // function to return the smallest // number with all digits even static int smallest_number(int n) { // iterate till we find a // number with all digits even for (int i = n; ; i++) if (check_digits(i) != 0) return i; } // Driver Code public static void Main() { int N = 2397; Console.WriteLine(smallest_number(N)); }}// This code is contributed by anuj_67. |
PHP
<?php// PHP program to print the smallest// integer not less than N with // all even digits// function to check if all digits// are even of a given numberfunction check_digits($n){ // iterate for all digits while ($n) { // if digit is odd if (($n % 10) % 2) return 0; $n /= 10; } // all digits are even return 1;}// function to return the// smallest number with // all digits evenfunction smallest_number( $n){ // iterate till we find a // number with all digits even for ($i = $n; ; $i++) if (check_digits($i)) return $i;} // Driver Code $N = 2397; echo smallest_number($N); // This code is contributed by m_kit?> |
Javascript
<script>// Javascript program to print the smallest// integer not less than N with all // even digits // function to check if all digits// are even of a given numberfunction check_digits(n){ // iterate for all digits while (n != 0) { // if digit is odd if ((n % 10) % 2 != 0) return 0; n = parseInt(n/10); } // all digits are even return 1;}// function to return the smallest// number with all digits evenfunction smallest_number(n){ // iterate till we find a // number with all digits even for (i = n; ; i++) if (check_digits(i) != 0) return i;}// Driver Codevar N = 2397;document.write(smallest_number(N));// This code is contributed by 29AjayKumar </script> |
Output
2400
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: We can find the number by increasing the first odd digit in N by one and replacing all digits to the right of that odd digit with the smallest even digit (i.e. 0). If there are no odd digits in N, then N is the smallest number itself. For example, consider N = 213. Increment first odd digit in N i.e., 1 to 2 and replace all digits right to it by 0. So, our required number will be 220.
Tricky Cases:
- If the first odd digit in N is 9, then we must replace the digit immediately to the left of that odd digit with the next even digit. For example, if N=44934, then smallest number=46000.
- Another tricky case is when the first odd digit is 9 and the digit directly to the left of the first odd digit is 8. In this case, we must replace the digit directly to the left of first odd digit by 0 and the digit left to this digit by next even digit, and keep doing this until we find a digit other than 8. For example, if N=86891, then Y=88000. Finally, if all digits to the left continue to be 8 until we reach the leftmost digit, or if the first digit of N is 9, then we must add the smallest non-zero even digit (i.e. 2) as a new digit on the left. For example, if N=891 or N=910, then Y=2000.
Below is the implementation of the efficient approach:
C++
// CPP program to print the smallest// integer not less than N with all even digits#include <bits/stdc++.h>using namespace std;// function to return the answer when the// first odd digit is 9int trickyCase(string s, int index){ int index1 = -1; // traverse towards the left to find the non-8 digit for (int i = index - 1; i >= 0; i--) { // index digit int digit = s[i] - '0'; // if digit is not 8, then break if (digit != 8) { index1 = i; break; } } // if on the left side of the '9', no 8 // is found then we return by adding a 2 and 0's if (index1 == -1) return 2 * pow(10, s.length()); int num = 0; // till non-8 digit add all numbers for (int i = 0; i < index1; i++) num = num * 10 + (s[i] - '0'); // if non-8 is even or odd than add the next even. if (s[index1] % 2 == 0) num = num * 10 + (s[index1] - '0' + 2); else num = num * 10 + (s[index1] - '0' + 1); // add 0 to right of 9 for (int i = index1 + 1; i < s.length(); i++) num = num * 10; return num;}// function to return the smallest number// with all digits evenint smallestNumber(int n){ int num = 0; string s = ""; int duplicate = n; // convert the number to string to // perform operations while (n) { s = char(n % 10 + 48) + s; n /= 10; } int index = -1; // find out the first odd number for (int i = 0; i < s.length(); i++) { int digit = s[i] - '0'; if (digit & 1) { index = i; break; } } // if no odd numbers are there, than n is the answer if (index == -1) return duplicate; // if the odd number is 9, // than tricky case handles it if (s[index] == '9') { num = trickyCase(s, index); return num; } // add all digits till first odd for (int i = 0; i < index; i++) num = num * 10 + (s[i] - '0'); // increase the odd digit by 1 num = num * 10 + (s[index] - '0' + 1); // add 0 to the right of the odd number for (int i = index + 1; i < s.length(); i++) num = num * 10; return num;}// Driver Codeint main(){ int N = 2397; cout << smallestNumber(N); return 0;} |
Java
// Java program to print the // smallest integer not less// than N with all even digitsimport java.io.*;import java.util.*;import java.lang.*;class GFG{// function to return // the answer when the// first odd digit is 9static int trickyCase(String s, int index){ int index1 = -1; // traverse towards the left // to find the non-8 digit for (int i = index - 1; i >= 0; i--) { // index digit int digit = s.charAt(i) - '0'; // if digit is not 8, // then break if (digit != 8) { index1 = i; break; } } // if on the left side of the // '9', no 8 is found then we // return by adding a 2 and 0's if (index1 == -1) return 2 * (int)Math.pow(10, s.length()); int num = 0; // till non-8 digit // add all numbers for (int i = 0; i < index1; i++) num = num * 10 + (s.charAt(i) - '0'); // if non-8 is even or odd // than add the next even. if (s.charAt(index1) % 2 == 0) num = num * 10 + (s.charAt(index1) - '0' + 2); else num = num * 10 + (s.charAt(index1) - '0' + 1); // add 0 to right of 9 for (int i = index1 + 1; i < s.length(); i++) num = num * 10; return num;}// function to return // the smallest number// with all digits evenstatic int smallestNumber(int n){ int num = 0; String s = ""; int duplicate = n; // convert the number to // string to perform operations while (n > 0) { s = (char)(n % 10 + 48) + s; n /= 10; } int index = -1; // find out the // first odd number for (int i = 0; i < s.length(); i++) { int digit = s.charAt(i) - '0'; int val = digit & 1; if (val == 1) { index = i; break; } } // if no odd numbers are there, // than n is the answer if (index == -1) return duplicate; // if the odd number is 9, // than tricky case handles it if (s.charAt(index) == '9') { num = trickyCase(s, index); return num; } // add all digits till first odd for (int i = 0; i < index; i++) num = num * 10 + (s.charAt(i) - '0'); // increase the // odd digit by 1 num = num * 10 + (s.charAt(index) - '0' + 1); // add 0 to the right // of the odd number for (int i = index + 1; i < s.length(); i++) num = num * 10; return num;}// Driver Codepublic static void main(String args[]){ int N = 2397; System.out.print(smallestNumber(N));}}// This code is contributed// by Akanksha rai(Abby_akku) |
Python3
# Python3 program to print the smallest# integer not less than N with all even digits# Function to return the answer when the# first odd digit is 9def trickyCase(s, index): index1 = -1; # traverse towards the left to find # the non-8 digit for i in range(index - 1, -1, -1): # index digit digit = s[i] - '0'; # if digit is not 8, then break if (digit != 8): index1 = i; break; # if on the left side of the '9', # no 8 is found then we return by # adding a 2 and 0's if (index1 == -1): return 2 * pow(10, len(s)); num = 0; # till non-8 digit add all numbers for i in range(index1): num = num * 10 + (s[i] - '0'); # if non-8 is even or odd # than add the next even. if (s[index1] % 2 == 0): num = num * 10 + (s[index1] - '0' + 2); else: num = num * 10 + (s[index1] - '0' + 1); # add 0 to right of 9 for i in range(index1 + 1, len(s)): num = num * 10; return num;# function to return the smallest # number with all digits evendef smallestNumber(n): num = 0; s = ""; duplicate = n; # convert the number to string to # perform operations while (n): s = chr(n % 10 + 48) + s; n = int(n / 10); index = -1; # find out the first odd number for i in range(len(s)): digit = ord(s[i]) - ord('0'); if (digit & 1): index = i; break; # if no odd numbers are # there, than n is the answer if (index == -1): return duplicate; # if the odd number is 9, than # tricky case handles it if (s[index] == '9'): num = trickyCase(s, index); return num; # add all digits till first odd for i in range(index): num = num * 10 + ord(s[i]) - ord('0'); # increase the odd digit by 1 num = num * 10 + (ord(s[index]) - ord('0') + 1); # add 0 to the right of the odd number for i in range(index + 1, len(s)): num = num * 10; return num;# Driver CodeN = 2397;print(smallestNumber(N));# This code is contributed# by mits |
C#
// C# program to print the smallest integer // not less than N with all even digitsusing System;class GFG{// function to return the answer when // the first odd digit is 9static int trickyCase(string s, int index){ int index1 = -1; // traverse towards the left // to find the non-8 digit for (int i = index - 1; i >= 0; i--) { // index digit int digit = s[i] - '0'; // if digit is not 8, then break if (digit != 8) { index1 = i; break; } } // if on the left side of the // '9', no 8 is found then we // return by adding a 2 and 0's if (index1 == -1) return 2 * (int)Math.Pow(10, s.Length); int num = 0; // till non-8 digit add all numbers for (int i = 0; i < index1; i++) num = num * 10 + (s[i] - '0'); // if non-8 is even or odd // than add the next even. if (s[index1] % 2 == 0) num = num * 10 + (s[index1] - '0' + 2); else num = num * 10 + (s[index1] - '0' + 1); // add 0 to right of 9 for (int i = index1 + 1; i < s.Length; i++) num = num * 10; return num;}// function to return the smallest number// with all digits evenstatic int smallestNumber(int n){ int num = 0; string s = ""; int duplicate = n; // convert the number to // string to perform operations while (n > 0) { s = (char)(n % 10 + 48) + s; n /= 10; } int index = -1; // find out the first odd number for (int i = 0; i < s.Length; i++) { int digit = s[i] - '0'; int val = digit & 1; if (val == 1) { index = i; break; } } // if no odd numbers are there, // than n is the answer if (index == -1) return duplicate; // if the odd number is 9, // than tricky case handles it if (s[index] == '9') { num = trickyCase(s, index); return num; } // add all digits till first odd for (int i = 0; i < index; i++) num = num * 10 + (s[i] - '0'); // increase the odd digit by 1 num = num * 10 + (s[index] - '0' + 1); // add 0 to the right of the odd number for (int i = index + 1; i < s.Length; i++) num = num * 10; return num;}// Driver Codepublic static void Main(){ int N = 2397; Console.Write(smallestNumber(N));}}// This code is contributed// by Akanksha Rai?> |
PHP
<?php// PHP program to print // the smallest integer// not less than N with// all even digits// function to return// the answer when the// first odd digit is 9function trickyCase($s, $index){ $index1 = -1; // traverse towards the // left to find the // non-8 digit for ($i = $index - 1; $i >= 0; $i--) { // index digit $digit = $s[$i] - '0'; // if digit is not // 8, then break if ($digit != 8) { $index1 = $i; break; } } // if on the left side // of the '9', no 8 // is found then we // return by adding a 2 // and 0's if ($index1 == -1) return 2 * pow(10, strlen($s)); $num = 0; // till non-8 digit // add all numbers for ($i = 0; $i < $index1; $i++) $num = $num * 10 + ($s[$i] - '0'); // if non-8 is even or // odd than add the next even. if ($s[$index1] % 2 == 0) $num = $num * 10 + ($s[$index1] - '0' + 2); else $num = $num * 10 + ($s[$index1] - '0' + 1); // add 0 to right of 9 for ($i = $index1 + 1; $i < strlen($s); $i++) $num = $num * 10; return $num;}// function to return// the smallest number// with all digits evenfunction smallestNumber($n){ $num = 0; $s = ""; $duplicate = $n; // convert the number // to string to perform // operations while ($n) { $s = chr($n % 10 + 48) . $s; $n = (int)($n / 10); } $index = -1; // find out the // first odd number for ($i = 0; $i < strlen($s); $i++) { $digit = $s[$i] - '0'; if ($digit & 1) { $index = $i; break; } } // if no odd numbers are // there, than n is the answer if ($index == -1) return $duplicate; // if the odd number // is 9, than tricky // case handles it if ($s[$index] == '9') { $num = trickyCase($s, $index); return $num; } // add all digits // till first odd for ($i = 0; $i < $index; $i++) $num = $num * 10 + ($s[$i] - '0'); // increase the // odd digit by 1 $num = $num * 10 + ($s[$index] - '0' + 1); // add 0 to the right // of the odd number for ($i = $index + 1; $i < strlen($s); $i++) $num = $num * 10; return $num;}// Driver Code$N = 2397;echo smallestNumber($N);// This code is contributed// by mits?> |
Javascript
<script> // Javascript program to print the smallest integer // not less than N with all even digits // function to return the answer when // the first odd digit is 9 function trickyCase(s, index) { let index1 = -1; // traverse towards the left // to find the non-8 digit for (let i = index - 1; i >= 0; i--) { // index digit let digit = s[i].charCodeAt() - '0'.charCodeAt(); // if digit is not 8, then break if (digit != 8) { index1 = i; break; } } // if on the left side of the // '9', no 8 is found then we // return by adding a 2 and 0's if (index1 == -1) return 2 * Math.pow(10, s.length); let num = 0; // till non-8 digit add all numbers for (let i = 0; i < index1; i++) num = num * 10 + (s[i].charCodeAt() - '0'.charCodeAt()); // if non-8 is even or odd // than add the next even. if (s[index1].charCodeAt() % 2 == 0) num = num * 10 + (s[index1].charCodeAt() - '0'.charCodeAt() + 2); else num = num * 10 + (s[index1].charCodeAt() - '0'.charCodeAt() + 1); // add 0 to right of 9 for (let i = index1 + 1; i < s.length; i++) num = num * 10; return num; } // function to return the smallest number // with all digits even function smallestNumber(n) { let num = 0; let s = ""; let duplicate = n; // convert the number to // string to perform operations while (n > 0) { s = String.fromCharCode(n % 10 + 48) + s; n = parseInt(n / 10, 10); } let index = -1; // find out the first odd number for (let i = 0; i < s.length; i++) { let digit = s[i].charCodeAt() - '0'.charCodeAt(); let val = digit & 1; if (val == 1) { index = i; break; } } // if no odd numbers are there, // than n is the answer if (index == -1) return duplicate; // if the odd number is 9, // than tricky case handles it if (s[index] == '9') { num = trickyCase(s, index); return num; } // add all digits till first odd for (let i = 0; i < index; i++) num = num * 10 + (s[i].charCodeAt() - '0'.charCodeAt()); // increase the odd digit by 1 num = num * 10 + (s[index].charCodeAt() - '0'.charCodeAt() + 1); // add 0 to the right of the odd number for (let i = index + 1; i < s.length; i++) num = num * 10; return num; } let N = 2397; document.write(smallestNumber(N)); // This code is contributed by divyeshrabadiya07.</script> |
Output
2400
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!
