Dado un número N, necesitamos escribir un programa para encontrar el número más pequeño no menor que N, que tiene todos los dígitos pares.
Ejemplos:
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.
Enfoque ingenuo : un enfoque ingenuo es seguir iterando desde N hasta que encontremos un número con todos los dígitos pares.
A continuación se muestra la implementación del enfoque anterior:
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 number
int 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 even
int 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 Code
int 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 digits
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 number def 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 even def 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 Code N = 2397 print (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 digits
using 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 number
function 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 even
function 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 number
function 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 even
function 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 Code
var N = 2397;
document.write(smallest_number(N));
// This code is contributed by 29AjayKumar
</script>
Producción:
2400
Complejidad del tiempo: O(N)
Enfoque eficiente: podemos encontrar el número aumentando el primer dígito impar en N en uno y reemplazando todos los dígitos a la derecha de ese dígito impar con el dígito par más pequeño (es decir, 0). Si no hay dígitos impares en N, entonces N es el número más pequeño. Por ejemplo, considere N = 213. Incremente el primer dígito impar en N, es decir, 1 a 2 y reemplace todos los dígitos por 0. Entonces, nuestro número requerido será 220.
Casos difíciles:
- Si el primer dígito impar en N es 9, entonces debemos reemplazar el dígito inmediatamente a la izquierda de ese dígito impar con el siguiente dígito par. Por ejemplo, si N=44934, entonces el número más pequeño=46000.
- Otro caso complicado es cuando el primer dígito impar es 9 y el dígito directamente a la izquierda del primer dígito impar es 8. En este caso, debemos reemplazar el dígito directamente a la izquierda del primer dígito impar por 0 y el dígito a la izquierda este dígito por el siguiente dígito par, y siga haciendo esto hasta que encontremos un dígito que no sea 8. Por ejemplo, si N=86891, entonces Y=88000. Finalmente, si todos los dígitos a la izquierda continúan siendo 8 hasta que alcancemos el dígito más a la izquierda, o si el primer dígito de N es 9, entonces debemos agregar el dígito par más pequeño distinto de cero (es decir, 2) como un nuevo dígito en el izquierda. Por ejemplo, si N=891 o N=910, entonces Y=2000.
A continuación se muestra la implementación del enfoque eficiente:
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 9
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 * 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 even
int 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 Code
int main()
{
int N = 2397;
cout << smallestNumber(N);
return 0;
}
Java
// Java program to print the
// smallest integer not less
// than N with all even digits
import java.io.*;
import java.util.*;
import java.lang.*;
class GFG
{
// function to return
// the answer when the
// first odd digit is 9
static 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 even
static 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 Code
public 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 9
def 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 even
def 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 Code
N = 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 digits
using System;
class GFG
{
// function to return the answer when
// the first odd digit is 9
static 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 even
static 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 Code
public 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 9
function 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 even
function 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>
Producción:
2400
Complejidad temporal: O(M), donde M es el número de dígitos de N.