Largest number not greater than N all the digits of which are odd
Given a number N, the task is to find the largest number not greater than N which has all of it’s digits as odd.
Examples:
Input: N = 23
Output: 19
19 is the largest number less than 23 which has all odd digits.
Input: N = 7236
Output: 7199
Naive Approach: Iterate from N to 0, and find the first number which has all of its digits as odd. This approach can still be optimized if the even numbers are skipped as every even number will have an even digit on it’s right.
Below is the implementation of the above approach:
C++
// CPP program to print the largest integer // not greater than N with all odd digits #include <bits/stdc++.h> using namespace std; // Function to check if all digits // of a number are odd bool allOddDigits( int n) { // iterate for all digits while (n) { // if digit is even if ((n % 10) % 2 == 0) return false ; n /= 10; } // all digits are odd return true ; } // function to return the largest number // with all digits odd int largestNumber( int n) { if (n % 2 == 0) n--; // iterate till we find a // number with all digits odd for ( int i = n;; i -= 2) if (allOddDigits(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 odd digits public class GFG{ // Function to check if all digits // of a number are odd static boolean allOddDigits( int n) { // iterate for all digits while (n != 0 ) { // if digit is even if ((n % 10 ) % 2 == 0 ) return false ; n /= 10 ; } // all digits are odd return true ; } // function to return the largest number // with all digits odd static int largestNumber( int n) { if (n % 2 == 0 ) n--; // iterate till we find a // number with all digits odd for ( int i = n;; i -= 2 ) if (allOddDigits(i)) return i; } public static void main(String []args){ int N = 23 ; System.out.println(largestNumber(N)); } // This code is contributed by ANKITRAI1 } |
Python3
# Python 3 program to print the largest # integer not greater than N with all # odd digits # Function to check if all digits # of a number are odd def allOddDigits(n): # iterate for all digits while (n): # if digit is even if ((n % 10 ) % 2 = = 0 ): return False n = int (n / 10 ) # all digits are odd return True # function to return the largest # number with all digits odd def largestNumber(n): if (n % 2 = = 0 ): n - = 1 # iterate till we find a # number with all digits odd i = n while ( 1 ): if (allOddDigits(i)): return i i - = 2 # Driver Code if __name__ = = '__main__' : N = 23 print (largestNumber(N)) # This code is contributed by # Shashank_Sharma |
C#
// C# program to print the largest // integer not greater than N with // all odd digits using System; class GFG { // Function to check if all // digits of a number are odd static bool allOddDigits( int n) { // iterate for all digits while (n != 0) { // if digit is even if ((n % 10) % 2 == 0) return false ; n /= 10; } // all digits are odd return true ; } // function to return the largest // number with all digits odd static int largestNumber( int n) { if (n % 2 == 0) n--; // iterate till we find a // number with all digits odd for ( int i = n;; i -= 2) if (allOddDigits(i)) return i; } // Driver Code public static void Main() { int N = 23; Console.WriteLine(largestNumber(N)); } } // This code is contributed by anuj_67 |
PHP
<?php // PHP program to print the largest integer // not greater than N with all odd digits // Function to check if all digits // of a number are odd function allOddDigits( $n ) { // iterate for all digits while ( $n > 1) { // if digit is even if (( $n % 10) % 2 == 0) return false; $n = (int) $n / 10; } // all digits are odd return true; } // function to return the largest // number with all digits odd function largestNumber( $n ) { if ( $n % 2 == 0) $n --; // iterate till we find a // number with all digits odd for ( $i = $n ;; $i = ( $i - 2)) if (allOddDigits( $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 odd digits // Function to check if all digits // of a number are odd function allOddDigits(n) { // iterate for all digits while (n != 0) { // if digit is even if ((n % 10) % 2 == 0) return false ; n = parseInt(n / 10); } // all digits are odd return true ; } // function to return the largest number // with all digits odd function largestNumber(n) { if (parseInt(n % 2) == 0) n--; // iterate till we find a // number with all digits odd for (i = n; i > 0; i -= 2) if (allOddDigits(i)) return i; } // Driver code var N = 23; document.write(largestNumber(N)); // This code is contributed by shikhasingrajput </script> |
19
Time Complexity: O(NlogN)
Auxiliary Space: O(1)
Efficient Approach: We can obtain the required number by decreasing the first even digit in N by one and then replacing all the other digits with the largest odd digit i.e. 9. For example, if N = 24578 then X = 19999. If there are no even 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 odd digits #include <bits/stdc++.h> using namespace std; // function to return the largest number // with all digits odd 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 even digit for ( int i = 0; i < s.length(); i++) { if (((s[i] - '0' ) % 2 & 1) == 0) { index = i; break ; } } // if no even digit, then N is the answer if (index == -1) return duplicate; int num = 0; // till first even digit, add all odd numbers for ( int i = 0; i < index; i++) num = num * 10 + (s[i] - '0' ); // decrease 1 from the even digit num = num * 10 + (s[index] - '0' - 1); // add 9 in the rest of the digits for ( int i = index + 1; i < s.length(); i++) num = num * 10 + 9; 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 odd digits class GFG { // function to return the largest number // with all digits odd 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 even digit for ( int i = 0 ; i < s.length(); i++) { if ((( int )(s.charAt(i) - '0' ) % 2 & 1 ) == 0 ) { index = i; break ; } } // if no even digit, then N is the answer if (index == - 1 ) return duplicate; int num = 0 ; // till first even digit, add all odd numbers for ( int i = 0 ; i < index; i++) num = num * 10 + ( int )(s.charAt(i) - '0' ); // decrease 1 from the even digit num = num * 10 + (( int )s.charAt(index) - ( int )( '0' ) - 1 ); // add 9 in the rest of the digits for ( int i = index + 1 ; i < s.length(); i++) num = num * 10 + 9 ; 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 odd digits # function to return the largest number # with all digits odd def largestNumber(n): s = "" duplicate = n # convert the number to a string for # easy operations while (n): s = chr (n % 10 + 48 ) + s n / / = 10 index = - 1 # find first even digit for i in range ( len (s)): if ((( ord (s[i]) - ord ( '0' )) % 2 & 1 ) = = 0 ): index = i break # if no even digit, then N is the answer if (index = = - 1 ): return duplicate num = 0 # till first even digit, # add all odd numbers for i in range (index): num = num * 10 + ( ord (s[i]) - ord ( '0' )) # decrease 1 from the even digit num = num * 10 + ( ord (s[index]) - ord ( '0' ) - 1 ) # add 9 in the rest of the digits for i in range (index + 1 , len (s)): num = num * 10 + 9 return num # Driver Code N = 24578 print (largestNumber(N)) # This code is contributed by mohit kumar |
C#
// C# program to print the largest integer // not greater than N with all odd digits using System; class GFG { // function to return the largest number // with all digits odd 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 even digit for ( int i = 0; i < s.Length; i++) { if ((( int )(s[i] - '0' ) % 2 & 1) == 0) { index = i; break ; } } // if no even digit, then N is the answer if (index == -1) return duplicate; int num = 0; // till first even digit, add all odd numbers for ( int i = 0; i < index; i++) num = num * 10 + ( int )(s[i] - '0' ); // decrease 1 from the even digit num = num * 10 + (( int )s[index] - ( int )( '0' ) - 1); // add 9 in the rest of the digits for ( int i = index + 1; i < s.Length; i++) num = num * 10 + 9; return num; } // Driver Code static void Main() { int N = 24578; Console.WriteLine(largestNumber(N)); } } // This code is contributed by mits |
Javascript
<script> // javascript program to print the largest integer // not greater than N with all odd digits // function to return the largest number // with all digits odd 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 even 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 even digit, then N is the answer if (index == -1) return duplicate; var num = 0; // till first even digit, add all odd numbers for (i = 0; i < index; i++) num = num * 10 + (s.charAt(i).charCodeAt(0) - '0' .charCodeAt(0)); // decrease 1 from the even digit num = num * 10 + (s.charAt(index).charCodeAt(0) - ( '0' ).charCodeAt(0) - 1); // add 9 in the rest of the digits for (i = index + 1; i < s.length; i++) num = num * 10 + 9; return num; } // Driver Code var N = 24578; document.write(largestNumber(N)); // This code contributed by Princi Singh </script> |
19999
Time Complexity: O(M) where M is the number of digits
Auxiliary Space: O(1)
Contact Us