Largest even digit number not greater than N
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 number int 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 even int largestNumber( int n) { // iterate till we find a // number with all digits even for ( int i = n;; i--) if (checkDigits(i)) return i; } // Driver Code int main() { int N = 23; cout << largestNumber(N); return 0; } |
Java
// Java program to print the largest // integer not greater than N with // all even digits import java .io.*; public class GFG { // function to check if all digits // are even of a given number static 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 even static 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 number def 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 even def 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 Code N = 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 digits using System; public class GFG { // function to check if all digits // are even of a given number static 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 even static 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 number function 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 even function 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 number function 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 even function largestNumber(n) { // iterate till we find a // number with all digits even for (i = n;; i--) if (checkDigits(i) > 0) return i; } // Driver Code var 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 even int 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 Code int main() { int N = 24578; cout << largestNumber(N); return 0; } |
Java
// Java program to print the largest // integer not greater than N with all even digits class GFG { // function to return the largest number // with all digits even static 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 Code public 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 digits import math as mt # function to return the largest # number with all digits even def 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 Code N = 24578 print (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 digits using System; class GFG { // function to return the largest number // with all digits even static 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 Code static 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 even function 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 even function 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 Code var 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.
Contact Us