Dado un entero positivo N , la tarea es encontrar el número mínimo de dígitos necesarios para eliminar para convertir N en un número impar cuya suma de dígitos sea par. Si es imposible hacerlo, imprima «No es posible».
Ejemplos:
Entrada: N = 12345
Salida: 1
Explicación:
Eliminar el dígito 3 modifica N a 1245.
Dado que la suma de los dígitos de N es 14 y N es impar, la salida requerida es 1.Entrada: N = 222
Salida: No posible
Enfoque: La idea es utilizar el hecho de que la suma de números pares de números impares da como resultado un número par. Siga los pasos a continuación para resolver el problema:
- Cuente el total de dígitos pares e impares presentes en el número entero N y guárdelos en variables, digamos pares e impares.
- Si Impar = 0 , entonces no se puede convertir el entero en un entero impar eliminando cualquier número de dígitos. Por lo tanto, imprima «No es posible» .
- De lo contrario, si Impar = 1 , para que la suma de los dígitos sea par, habrá que eliminar ese dígito impar, lo que da como resultado un número par. Por lo tanto, imprima » No es posible».
- Ahora, cuente el número de dígitos que se eliminarán después de la última aparición de un dígito impar y guárdelo en una variable, digamos ans .
- Si Odd es impar, entonces incremente el conteo de ans en uno, ya que tendrá que eliminar un dígito impar para que la suma sea par.
- Finalmente, imprima y si ninguno de los casos anteriores satisface.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum count of digits
// required to be remove to make N odd and
// the sum of digits of N even
void minOperations(string& N)
{
// Stores count of even digits
int even = 0;
// Stores count of odd digits
int odd = 0;
// Iterate over the digits of N
for (auto it : N) {
// If current digit is even
if ((it - '0') % 2 == 0) {
// Update even
even++;
}
// Otherwise
else {
// Update odd
odd++;
}
}
// Base conditions
if (odd == 0 || odd == 1) {
cout << "Not Possible"
<< "\n";
}
else {
// Stores count of digits required to be
// removed to make N odd and the sum of
// digits of N even
int ans = 0;
// Iterate over the digits of N
for (auto it : N) {
// If current digit is even
if ((it - '0') % 2 == 0) {
// Update ans
ans++;
}
// Otherwise,
else {
// Update ans
ans = 0;
}
}
// If count of odd digits is odd
if (odd % 2) {
// Update ans
ans++;
}
// Finally print the ans
cout << ans << endl;
}
}
// Driver code
int main()
{
// Input string
string N = "12345";
// Function call
minOperations(N);
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG
{
// Function to find minimum count of digits
// required to be remove to make N odd and
// the sum of digits of N even
static void minOperations(String N)
{
// Stores count of even digits
int even = 0;
// Stores count of odd digits
int odd = 0;
// Iterate over the digits of N
for (int it : N.toCharArray())
{
// If current digit is even
if ((it - '0') % 2 == 0)
{
// Update even
even++;
}
// Otherwise
else
{
// Update odd
odd++;
}
}
// Base conditions
if (odd == 0 || odd == 1)
{
System.out.print("Not Possible"
+ "\n");
}
else
{
// Stores count of digits required to be
// removed to make N odd and the sum of
// digits of N even
int ans = 0;
// Iterate over the digits of N
for (int it : N.toCharArray())
{
// If current digit is even
if ((it - '0') % 2 == 0)
{
// Update ans
ans++;
}
// Otherwise,
else
{
// Update ans
ans = 0;
}
}
// If count of odd digits is odd
if (odd % 2 != 0)
{
// Update ans
ans++;
}
// Finally print the ans
System.out.print(ans +"\n");
}
}
// Driver code
public static void main(String[] args)
{
// Input String
String N = "12345";
// Function call
minOperations(N);
}
}
// This code is contributed by shikhasingrajput.
Python3
# Python implementation of the above approach
# Function to find minimum count of digits
# required to be remove to make N odd and
# the sum of digits of N even
def minOperations(N):
# Stores count of even digits
even = 0;
# Stores count of odd digits
odd = 0;
# Iterate over the digits of N
for it in N:
# If current digit is even
if (int(ord(it) - ord('0')) % 2 == 0):
# Update even
even += 1;
# Otherwise
else:
# Update odd
odd += 1;
# Base conditions
if (odd == 0 or odd == 1):
print("Not Possible" + "");
else:
# Stores count of digits required to be
# removed to make N odd and the sum of
# digits of N even
ans = 0;
# Iterate over the digits of N
for it in N:
# If current digit is even
if (int(ord(it) - ord('0')) % 2 == 0):
# Update ans
ans += 1;
# Otherwise,
else:
# Update ans
ans = 0;
# If count of odd digits is odd
if (odd % 2 != 0):
# Update ans
ans += 1;
# Finally print the ans
print(ans, end=" ");
# Driver code
if __name__ == '__main__':
# Input String
N = "12345";
# Function call
minOperations(N);
# This code is contributed by shikhasingrajput
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to find minimum count of digits
// required to be remove to make N odd and
// the sum of digits of N even
static void minOperations(String N)
{
// Stores count of even digits
int even = 0;
// Stores count of odd digits
int odd = 0;
// Iterate over the digits of N
foreach (int it in N.ToCharArray())
{
// If current digit is even
if ((it - '0') % 2 == 0)
{
// Update even
even++;
}
// Otherwise
else
{
// Update odd
odd++;
}
}
// Base conditions
if (odd == 0 || odd == 1)
{
Console.Write("Not Possible"
+ "\n");
}
else
{
// Stores count of digits required to be
// removed to make N odd and the sum of
// digits of N even
int ans = 0;
// Iterate over the digits of N
foreach (int it in N.ToCharArray())
{
// If current digit is even
if ((it - '0') % 2 == 0)
{
// Update ans
ans++;
}
// Otherwise,
else
{
// Update ans
ans = 0;
}
}
// If count of odd digits is odd
if (odd % 2 != 0)
{
// Update ans
ans++;
}
// Finally print the ans
Console.Write(ans +"\n");
}
}
// Driver code
public static void Main(String[] args)
{
// Input String
String N = "12345";
// Function call
minOperations(N);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript implementation of the above approach
// Function to find minimum count of digits
// required to be remove to make N odd and
// the sum of digits of N even
function minOperations(N)
{
// Stores count of even digits
var even = 0;
// Stores count of odd digits
var odd = 0;
// Iterate over the digits of N
for (var it =0; it<N.length; it++) {
// If current digit is even
if ((N[it] - '0') % 2 == 0) {
// Update even
even++;
}
// Otherwise
else {
// Update odd
odd++;
}
}
// Base conditions
if (odd == 0 || odd == 1) {
document.write( "Not Possible"
+ "<br>");
}
else {
// Stores count of digits required to be
// removed to make N odd and the sum of
// digits of N even
var ans = 0;
// Iterate over the digits of N
for (var it =0; it<N.length; it++){
// If current digit is even
if ((N[it] - '0') % 2 == 0) {
// Update ans
ans++;
}
// Otherwise,
else {
// Update ans
ans = 0;
}
}
// If count of odd digits is odd
if (odd % 2) {
// Update ans
ans++;
}
// Finally print the ans
document.write( ans );
}
}
// Driver code
// Input string
var N = "12345";
// Function call
minOperations(N);
</script>
Producción:
1
Complejidad de tiempo: O(log 10 (N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA