Largest even digit number not greater than N

0 0 10 minutes read

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:

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:

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 zambiatek!