Dado un gran número en forma de string str . La tarea es encontrar el número impar más pequeño cuya suma de dígitos sea par eliminando cero o más caracteres de la string dada str , donde los dígitos se pueden reorganizar.
Ejemplos
Entrada: str = “15470”
Salida: 15
Explicación:
Los dos dígitos impares más pequeños son 1 y 5. Por lo tanto, el número requerido es 15.Entrada: str = “124”
Salida: -1
Explicación:
No hay ningún dígito impar más pequeño que no sea 1. Por lo tanto, el número requerido no se puede formar.
Planteamiento:
Al observar de cerca, por intuición, se puede entender que el número de dígitos en el número impar más pequeño posible es 2. Y cada dígito en este número es impar porque la suma de dos dígitos impares siempre es par. Por lo tanto, la idea para resolver este problema es iterar a través de la string dada y almacenar todos los números impares en una array. Esta array se puede ordenar y los dos primeros dígitos juntos forman el número impar más pequeño cuya suma de dígitos es par.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find the smallest odd number
// with even sum of digits from the given number N
#include<bits/stdc++.h>
using namespace std;
// Function to find the smallest odd number
// whose sum of digits is even from the given string
int smallest(string s)
{
// Converting the given string
// to a list of digits
vector<int> a(s.length());
for(int i = 0; i < s.length(); i++)
a[i] = s[i]-'0';
// An empty array to store the digits
vector<int> b;
// For loop to iterate through each digit
for(int i = 0; i < a.size(); i++)
{
// If the given digit is odd then
// the digit is appended to the array b
if((a[i]) % 2 != 0)
b.push_back(a[i]);
}
// Sorting the list of digits
sort(b.begin(),b.end());
// If the size of the list is greater than 1
// then a 2 digit smallest odd number is returned
// Since the sum of two odd digits is always even
if(b.size() > 1)
return (b[0])*10 + (b[1]);
// Else, -1 is returned
return -1;
}
// Driver code
int main()
{
cout << (smallest("15470"));
}
// This code is contributed by Surendra_Gangwar
Java
// Java program to find the smallest
// odd number with even sum of digits
// from the given number N
import java.util.*;
class GFG{
// Function to find the smallest
// odd number whose sum of digits
// is even from the given string
public static int smallest(String s)
{
// Converting the given string
// to a list of digits
int[] a = new int[s.length()];
for(int i = 0; i < s.length(); i++)
a[i] = s.charAt(i) - '0';
// An empty array to store the digits
Vector<Integer> b = new Vector<Integer>();
// For loop to iterate through each digit
for(int i = 0; i < a.length; i++)
{
// If the given digit is odd
// then the digit is appended
// to the array b
if(a[i] % 2 != 0)
b.add(a[i]);
}
// Sorting the list of digits
Collections.sort(b);
// If the size of the list is greater
// than 1 then a 2 digit smallest odd
// number is returned. Since the sum
// of two odd digits is always even
if(b.size() > 1)
return (b.get(0)) * 10 + (b.get(1));
// Else, -1 is returned
return -1;
}
// Driver code
public static void main(String[] args)
{
System.out.print(smallest("15470"));
}
}
// This code is contributed by divyeshrabadiya07
Python
# Python program to find the smallest odd number
# with even sum of digits from the given number N
# Function to find the smallest odd number
# whose sum of digits is even from the given string
def smallest(s):
# Converting the given string
# to a list of digits
a = list(s)
# An empty array to store the digits
b = []
# For loop to iterate through each digit
for i in range(len(a)):
# If the given digit is odd then
# the digit is appended to the array b
if(int(a[i])%2 != 0):
b.append(a[i])
# Sorting the list of digits
b = sorted(b)
# If the size of the list is greater than 1
# then a 2 digit smallest odd number is returned
# Since the sum of two odd digits is always even
if(len(b)>1):
return int(b[0])*10 + int(b[1])
# Else, -1 is returned
return -1
# Driver code
if __name__ == "__main__":
print(smallest("15470"))
C#
// C# program to find the smallest
// odd number with even sum of digits
// from the given number N
using System;
using System.Collections;
class GFG{
// Function to find the smallest
// odd number whose sum of digits
// is even from the given string
public static int smallest(string s)
{
// Converting the given string
// to a list of digits
int[] a = new int[s.Length];
for(int i = 0; i < s.Length; i++)
a[i] = (int)(s[i] - '0');
// An empty array to store the digits
ArrayList b = new ArrayList();
// For loop to iterate through each digit
for(int i = 0; i < a.Length; i++)
{
// If the given digit is odd
// then the digit is appended
// to the array b
if (a[i] % 2 != 0)
b.Add(a[i]);
}
// Sorting the list of digits
b.Sort();
// If the size of the list is greater
// than 1 then a 2 digit smallest odd
// number is returned. Since the sum
// of two odd digits is always even
if (b.Count > 1)
return ((int)b[0] * 10 + (int)b[1]);
// Else, -1 is returned
return -1;
}
// Driver code
public static void Main(string[] args)
{
Console.Write(smallest("15470"));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to find the
// smallest odd number with even
// sum of digits from the given number N
// Function to find the smallest odd
// number whose sum of digits is even
// from the given string
function smallest(s)
{
// Converting the given string
// to a list of digits
var a = Array(s.length);
for(var i = 0; i < s.length; i++)
a[i] = s[i].charCodeAt(0) -
'0'.charCodeAt(0);
// An empty array to store the digits
var b = [];
// For loop to iterate through each digit
for(var i = 0; i < a.length; i++)
{
// If the given digit is odd then
// the digit is appended to the array b
if ((a[i]) % 2 != 0)
b.push(a[i]);
}
// Sorting the list of digits
b.sort((a, b) => a - b);
// If the size of the list is greater
// than 1 then a 2 digit smallest odd
// number is returned. Since the sum
// of two odd digits is always even
if (b.length > 1)
return (b[0]) * 10 + (b[1]);
// Else, -1 is returned
return -1;
}
// Driver code
document.write(smallest("15470"));
// This code is contributed by importantly
</script>
15
Complejidad de tiempo: O(N) donde N = longitud de la string.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Ripunjoy Medhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA