Given a number N, we need to write a program to find the largest number not greater than N which has all digits even.
Examples:
Input: N = 23 Output: 22 Explanation: 22 is the largest number not greater than N which has all digits even. Input: N = 236 Output: 228 Explanation: 228 is the largest number not greater than N which has all digits even.
Naive Approach: A naive approach is to iterate from N to 0, and find the first number which has all of its digits even.
Below is the implementation of the above approach:
C++
// CPP program to print the largest// integer not greater 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 checkDigits(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 largest number// with all digits evenint largestNumber(int n){ // iterate till we find a // number with all digits even for (int i = n;; i--) if (checkDigits(i)) return i;}// Driver Codeint main(){ int N = 23; cout << largestNumber(N); return 0;} |
Java
// Java program to print the largest// integer not greater than N with // all even digitsimport java .io.*;public class GFG { // function to check if all digits// are even of a given numberstatic int checkDigits(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 largest // number with all digits evenstatic int largestNumber(int n){ // iterate till we find a // number with all digits even for (int i = n;; i--) if (checkDigits(i) > 0) return i;} // Driver Code static public void main (String[] args) { int N = 23; System.out.println(largestNumber(N)); }}// This code is contributed by vt_m. |
Python3
# Python3 program to print the largest# integer not greater than N with # all even digits# function to check if all digits# are even of a given numberdef checkDigits(n): # iterate for all digits while (n>0): # if digit is odd if ((n % 10) % 2): return False; n =int(n/10); # all digits are even return True;# function to return the# largest number with# all digits evendef largestNumber(n): # Iterate till we find a # number with all digits even for i in range(n,-1,-1): if (checkDigits(i)): return i;# Driver CodeN = 23; print(largestNumber(N));# This code is contributed by mits |
C#
// C# program to print the largest// integer not greater than N with // all even digitsusing System;public class GFG { // function to check if all digits// are even of a given numberstatic int checkDigits(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 largest // number with all digits evenstatic int largestNumber(int n){ // iterate till we find a // number with all digits even for (int i = n;; i--) if (checkDigits(i) > 0) return i;} // Driver Code static public void Main () { int N = 23; Console.WriteLine(largestNumber(N)); }}// This code is contributed by aunj_67. |
PHP
<?php// PHP program to print the largest// integer not greater than N with // all even digits// function to check if all digits// are even of a given numberfunction checkDigits($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// largest number with// all digits evenfunction largestNumber($n){ // Iterate till we find a // number with all digits even for ($i = $n; ; $i--) if (checkDigits($i)) return $i;}// Driver Code$N = 23; echo(largestNumber($N));// This code is contributed by Ajit.?> |
Javascript
<script>// javascript program to print the largest// integer not greater than N with // all even digits// function to check if all digits// are even of a given numberfunction checkDigits(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 largest // number with all digits evenfunction largestNumber(n){ // iterate till we find a // number with all digits even for (i = n;; i--) if (checkDigits(i) > 0) return i;}// Driver Codevar N = 23; document.write(largestNumber(N));// This code is contributed by shikhasingrajput </script> |
Output:
22
Time Complexity: O(N)
Efficient Approach: We can obtain the required number by decreasing the first odd digit in N by one and then replacing all digits to the right of that odd digit with the largest even digit (i.e. 8). For example, if N = 24578, then X = 24488. In some cases, this approach can create a leading 0, we can simply drop the leading 0 in that case. For example, if N = 1334 then X = 0888. So, our answer will be X = 888. If there are no odd digits in N, then N is the number itself.
Below is the implementation of the above approach:
C++
// CPP program to print the largest// integer not greater than N with all even digits#include <bits/stdc++.h>using namespace std;// function to return the largest number// with all digits evenint largestNumber(int n){ string s = ""; int duplicate = n; // convert the number to a string for // easy operations while (n) { s = char(n % 10 + 48) + s; n /= 10; } int index = -1; // find first odd digit for (int i = 0; i < s.length(); i++) { if ((s[i] - '0') % 2 & 1) { index = i; break; } } // if no digit, then N is the answer if (index == -1) return duplicate; int num = 0; // till first odd digit, add all even numbers for (int i = 0; i < index; i++) num = num * 10 + (s[i] - '0'); // decrease 1 from the odd digit num = num * 10 + (s[index] - '0' - 1); // add 0 in the rest of the digits for (int i = index + 1; i < s.length(); i++) num = num * 10 + 8; return num;}// Driver Codeint main(){ int N = 24578; cout << largestNumber(N); return 0;} |
Java
// Java program to print the largest// integer not greater than N with all even digitsclass GFG{ // function to return the largest number// with all digits evenstatic int largestNumber(int n){ String s = ""; int duplicate = n; // convert the number to a string for // easy operations while (n > 0) { s = (char)(n % 10 + 48) + s; n /= 10; } int index = -1; // find first odd digit for (int i = 0; i < s.length(); i++) { if ((((int)(s.charAt(i) - '0') % 2) & 1) > 0) { index = i; break; } } // if no digit, then N is the answer if (index == -1) return duplicate; int num = 0; // till first odd digit, add all even numbers for (int i = 0; i < index; i++) num = num * 10 + (int)(s.charAt(i) - '0'); // decrease 1 from the odd digit num = num * 10 + ((int)s.charAt(index) - (int)('0') - 1); // add 0 in the rest of the digits for (int i = index + 1; i < s.length(); i++) num = num * 10 + 8; return num;}// Driver Codepublic static void main (String[] args){ int N = 24578; System.out.println(largestNumber(N));}}// This code is contributed by mits |
Python3
# Python3 program to print the largest# integer not greater than N with # all even digitsimport math as mt# function to return the largest # number with all digits evendef largestNumber(n): s = "" duplicate = n # convert the number to a string # for easy operations while (n > 0): s = chr(n % 10 + 48) + s n = n // 10 index = -1 # find first odd digit for i in range(len(s)): if ((ord(s[i]) - ord('0')) % 2 & 1): index = i break # if no digit, then N is the answer if (index == -1): return duplicate num = 0 # till first odd digit, add all # even numbers for i in range(index): num = num * 10 + (ord(s[i]) - ord('0')) # decrease 1 from the odd digit num = num * 10 + (ord(s[index]) - ord('0') - 1) # add 0 in the rest of the digits for i in range(index+1,len(s)): num = num * 10 + 8 return num# Driver CodeN = 24578print(largestNumber(N))# This code is contributed # by Mohit kumar 29 |
C#
// C# program to print the largest// integer not greater than N with all even digitsusing System;class GFG{ // function to return the largest number// with all digits evenstatic int largestNumber(int n){ string s = ""; int duplicate = n; // convert the number to a string for // easy operations while (n > 0) { s = (char)(n % 10 + 48) + s; n /= 10; } int index = -1; // find first odd digit for (int i = 0; i < s.Length; i++) { if ((((int)(s[i] - '0') % 2) & 1) > 0) { index = i; break; } } // if no digit, then N is the answer if (index == -1) return duplicate; int num = 0; // till first odd digit, add all even numbers for (int i = 0; i < index; i++) num = num * 10 + (int)(s[i] - '0'); // decrease 1 from the odd digit num = num * 10 + ((int)s[index] - (int)('0') - 1); // add 0 in the rest of the digits for (int i = index + 1; i < s.Length; i++) num = num * 10 + 8; return num;}// Driver Codestatic void Main(){ int N = 24578; Console.WriteLine(largestNumber(N));}}// This code is contributed by mits |
PHP
<?php// PHP program to print the largest// integer not greater than N with all even digits// function to return the largest number// with all digits evenfunction largestNumber($n){ $s = ""; $duplicate = $n; // convert the number to a string for // easy operations while ($n) { $s = chr($n % 10 + 48).$s; $n =(int)($n/10); } $index = -1; // find first odd digit for ($i = 0; $i < strlen($s); $i++) { if (ord($s[$i] - '0') % 2 & 1) { $index = $i; break; } } // if no digit, then N is the answer if ($index == -1) return $duplicate; $num = 0; // till first odd digit, add all even numbers for ($i = 0; $i < $index; $i++) $num = $num * 10 + (ord($s[$i]) - ord('0')); // decrease 1 from the odd digit $num = $num * 10 + ((ord($s[$i]) - ord('0')) - 1); // add 0 in the rest of the digits for ($i = $index + 1; $i < strlen($s); $i++) $num = $num * 10 + 8; return $num;}// Driver Code $N = 24578; echo largestNumber($N);// This code is contributed by mits?> |
Javascript
<script>// javascript program to print the largest// integer not greater than N with all even digits // function to return the largest number// with all digits evenfunction largestNumber(n){ var s = ""; var duplicate = n; // convert the number to a string for // easy operations while (n > 0) { s = String.fromCharCode(n % 10 + 48) + s; n = parseInt(n/10); } var index = -1; // find first odd digit for (i = 0; i < s.length; i++) { if ((((s.charAt(i).charCodeAt(0) - '0'.charCodeAt(0)) % 2) & 1) > 0) { index = i; break; } } // if no digit, then N is the answer if (index == -1) return duplicate; var num = 0; // till first odd digit, add all even numbers for (i = 0; i < index; i++) num = num * 10 + (s.charAt(i).charCodeAt(0) - '0'.charCodeAt(0)); // decrease 1 from the odd digit num = num * 10 + (s.charAt(index).charCodeAt(0) - ('0').charCodeAt(0) - 1); // add 0 in the rest of the digits for (i = index + 1; i < s.length; i++) num = num * 10 + 8; return num;}// Driver Codevar N = 24578;document.write(largestNumber(N));// This code contributed by shikhasingrajput</script> |
Output:
24488
Time Complexity: O(M), where M is the number of digits
Space complexity of the given program is O(logN), as the input integer N is converted to a string s of size logN for easy operations. The other variables used in the program take constant space.
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!
