Dado un número N , la tarea es encontrar el número más grande que no sea mayor que N y que tenga todos sus dígitos impares .
Ejemplos:
Entrada: N = 23
Salida: 19
19 es el número más grande menor que 23 que tiene todos los dígitos impares.
Entrada: N = 7236
Salida: 7199
Enfoque ingenuo : iterar de N a 0 y encontrar el primer número que tiene todos sus dígitos impares. Este enfoque aún se puede optimizar si se omiten los números pares, ya que cada número par tendrá un dígito par a la derecha.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
19
Complejidad de tiempo: O (NlogN)
Espacio auxiliar: O(1)
Enfoque eficiente: Podemos obtener el número requerido disminuyendo el primer dígito par en N en uno y luego reemplazando todos los demás dígitos con el dígito impar más grande, es decir , 9 . Por ejemplo, si N = 24578 entonces X = 19999 . Si no hay dígitos pares en N , entonces N es el número en sí.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
19999
Complejidad de tiempo: O(M) donde M es el número de dígitos
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA