Dado un número entero N , la tarea es reducir el número al número entero positivo más pequeño X después de eliminar algunos de los dígitos (posiblemente ninguno) de modo que X sea divisible por 4 . Imprime -1 si no se puede reducir a dicho múltiplo.
Ejemplos:
Entrada: N = 78945666384
Salida: 4
Elimina todos los dígitos excepto una única
aparición del dígito ‘4’.
Entrada: N = 17
Salida: -1
Enfoque: Ya que el número resultante tiene que ser minimizado. Por lo tanto, verifique si hay algún dígito en el número que sea igual a ‘4’ u ‘8’ porque estos son los dígitos divisibles por 4 en orden ascendente. Si no hay tales dígitos, compruebe todas las subsecuencias de dígitos de longitud 2 para cualquier múltiplo de 4 . Si todavía no hay un múltiplo de 4 , entonces el número no es posible porque cualquier número con más de 2 dígitos que sea un múltiplo de 4 definitivamente tendrá una subsecuencia divisible por 4 con dígitos menos de 3 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int TEN = 10;
// Function to return the minimum number
// that can be formed after removing
// the digits which is a multiple of 4
int minNum(string str, int len)
{
int res = INT_MAX;
// For every digit of the number
for (int i = 0; i < len; i++) {
// Check if the current digit
// is divisible by 4
if (str[i] == '4' || str[i] == '8') {
res = min(res, str[i] - '0');
}
}
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
int num = (str[i] - '0') * TEN
+ (str[j] - '0');
// If any subsequence of two
// digits is divisible by 4
if (num % 4 == 0) {
res = min(res, num);
}
}
}
return ((res == INT_MAX) ? -1 : res);
}
// Driver code
int main()
{
string str = "17";
int len = str.length();
cout << minNum(str, len);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int TEN = 10;
// Function to return the minimum number
// that can be formed after removing
// the digits which is a multiple of 4
static int minNum(char[] str, int len)
{
int res = Integer.MAX_VALUE;
// For every digit of the number
for (int i = 0; i < len; i++)
{
// Check if the current digit
// is divisible by 4
if (str[i] == '4' || str[i] == '8')
{
res = Math.min(res, str[i] - '0');
}
}
for (int i = 0; i < len - 1; i++)
{
for (int j = i + 1; j < len; j++)
{
int num = (str[i] - '0') * TEN
+ (str[j] - '0');
// If any subsequence of two
// digits is divisible by 4
if (num % 4 == 0)
{
res = Math.min(res, num);
}
}
}
return ((res == Integer.MAX_VALUE) ? -1 : res);
}
// Driver code
public static void main(String[] args)
{
String str = "17";
int len = str.length();
System.out.print(minNum(str.toCharArray(), len));
}
}
// This code is contributed by 29AjayKumar
Python 3
# Python3 implementation of the approach
import sys
TEN = 10
# Function to return the minimum number
# that can be formed after removing
# the digits which is a multiple of 4
def minNum(str, len1):
res = sys.maxsize
# For every digit of the number
for i in range(len1):
# Check if the current digit
# is divisible by 4
if (str[i] == '4' or str[i] == '8'):
res = min(res, ord(str[i]) - ord('0'))
for i in range(len1 - 1):
for j in range(i + 1, len1, 1):
num = (ord(str[i]) - ord('0')) * TEN + \
(ord(str[j]) - ord('0'))
# If any subsequence of two
# digits is divisible by 4
if (num % 4 == 0):
res = min(res, num)
if (res == sys.maxsize):
return -1
else:
return res
# Driver code
if __name__ == '__main__':
str = "17"
len1 = len(str)
print(minNum(str, len1))
# This code is contributed by Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
static int TEN = 10;
// Function to return the minimum number
// that can be formed after removing
// the digits which is a multiple of 4
static int minNum(char[] str, int len)
{
int res = int.MaxValue;
// For every digit of the number
for (int i = 0; i < len; i++)
{
// Check if the current digit
// is divisible by 4
if (str[i] == '4' || str[i] == '8')
{
res = Math.Min(res, str[i] - '0');
}
}
for (int i = 0; i < len - 1; i++)
{
for (int j = i + 1; j < len; j++)
{
int num = (str[i] - '0') * TEN
+ (str[j] - '0');
// If any subsequence of two
// digits is divisible by 4
if (num % 4 == 0)
{
res = Math.Min(res, num);
}
}
}
return ((res == int.MaxValue) ? -1 : res);
}
// Driver code
public static void Main(String[] args)
{
String str = "17";
int len = str.Length;
Console.Write(minNum(str.ToCharArray(), len));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript implementation of the approach
var TEN = 10;
// Function to return the minimum number
// that can be formed after removing
// the digits which is a multiple of 4
function minNum( str , len) {
var res = Number.MAX_VALUE;
// For every digit of the number
for (var i = 0; i < len; i++) {
// Check if the current digit
// is divisible by 4
if (str[i] == '4' || str[i] == '8') {
res = Math.min(res, str[i] - '0');
}
}
for (i = 0; i < len - 1; i++) {
for (j = i + 1; j < len; j++) {
var num = (str[i] - '0') * TEN + (str[j] - '0');
// If any subsequence of two
// digits is divisible by 4
if (num % 4 == 0) {
res = Math.min(res, num);
}
}
}
return ((res == Number.MAX_VALUE) ? -1 : res);
}
// Driver code
var str = "17";
var len = str.length;
document.write(minNum(str, len));
// This code is contributed by umadevi9616.
</script>
-1
Publicación traducida automáticamente
Artículo escrito por SnehashishKalamkar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA