Dado un número entero N , la tarea es encontrar el número mínimo de intercambios requeridos para hacer que N sea divisible por 60. Si no es posible, imprima “ -1 ”.
Ejemplos:
Entrada: N = 603
Salida: 2
Explicación:
Se requieren dos operaciones de intercambio:
En el primer intercambio (0, 3): 630
En el segundo intercambio (6, 3): 360
Ahora 360 es divisible por 60.
Por lo tanto, el mínimo de dos intercambios son requeridos.
Entrada: N = 205
Salida: -1
Acercarse:
- Para que un número sea divisible por 60, debe ser divisible por 2, 3 y 10. Por lo tanto:
- Si la suma de los dígitos de un número no es divisible por 3, o
- Si no hay dígitos que sean divisibles por 2, o
- Si el número no contiene ningún 0,
- Luego, el número mínimo de intercambios requeridos se puede determinar mediante las siguientes reglas:
- Si el número ya es divisible por 60, entonces se requieren 0 intercambios . Esto se puede determinar si el último dígito (LSB) es 0 y el penúltimo dígito es divisible por 2.
- Si cualquiera de los siguientes casos es cierto, entonces se requiere 1 intercambio .
- Si el último dígito (LSB) es 0 y el penúltimo dígito no es divisible por 2, o el último dígito (LSB) es divisible por 2 y el penúltimo dígito es 0.
- Si el último dígito (LSB) es 0 y el penúltimo dígito no es divisible por 2, y hay más de 1 cero presente en el número.
- De lo contrario, se requieren 2 intercambios
A continuación se muestra la implementación del enfoque anterior.
CPP
// C++ program to find minimum number
// of swap operations required
#include <bits/stdc++.h>
using namespace std;
// Function that print minimum number
// of swap operations required
void MinimumSwapOperations(string s)
{
bool zero_exist = false;
bool multiple_of_2 = false;
int sum = 0;
int index_of_zero;
bool more_zero = false;
for (int i = 0; i < s.length(); i++) {
int val = s[i] - '0';
// Condition if more than one
// zero exist
if (zero_exist == true)
more_zero = true;
// Condition if zero_exist
if (val == 0) {
zero_exist = true;
index_of_zero = i;
}
// Computing total sum of all digits
sum += val;
}
// Condition if zero does not exist or
// the sum is not divisible by 3
if (zero_exist == false || sum % 3 != 0) {
cout << "-1"
<< "\n";
return;
}
for (int i = 0; i < s.length(); i++) {
int val = s[i] - '0';
// Condition to find a digit that is
// multiple of 2 other than one zero
if (val % 2 == 0 && i != index_of_zero)
multiple_of_2 = true;
}
// Condition if multiple of 2
// do not exist
if (multiple_of_2 == false) {
cout << "-1"
<< "\n";
return;
}
int last_val = s[s.length() - 1] - '0';
int second_last_val = s[s.length() - 2]
- '0';
// Condition for zero swaps
// means the number is already
// is divisible by 60
if (last_val == 0
&& second_last_val % 2 == 0)
cout << 0 << "\n";
// Condition for only one swap
else if ((last_val == 0
&& second_last_val % 2 != 0)
|| (last_val % 2 == 0
&& second_last_val == 0))
cout << 1 << "\n";
else if (more_zero == true
&& (last_val == 0
&& second_last_val % 2 != 0))
cout << 1 << "\n";
// Otherwise 2 swaps required
else
cout << 2 << "\n";
}
// Driver Code
int main()
{
string N = "20";
MinimumSwapOperations(N);
return 0;
}
Java
// Java program to find minimum number
// of swap operations required
class GFG {
// Function that print minimum number
// of swap operations required
static void MinimumSwapOperations(String s)
{
boolean zero_exist = false;
boolean multiple_of_2 = false;
int sum = 0;
int index_of_zero = 0;
boolean more_zero = false;
for (int i = 0; i < s.length(); i++) {
int val = s.charAt(i) - '0';
// Condition if more than one
// zero exist
if (zero_exist == true)
more_zero = true;
// Condition if zero_exist
if (val == 0) {
zero_exist = true;
index_of_zero = i;
}
// Computing total sum of all digits
sum += val;
}
// Condition if zero does not exist or
// the sum is not divisible by 3
if (zero_exist == false || sum % 3 != 0) {
System.out.println("-1");
return;
}
for (int i = 0; i < s.length(); i++) {
int val = s.charAt(i) - '0';
// Condition to find a digit that is
// multiple of 2 other than one zero
if (val % 2 == 0 && i != index_of_zero)
multiple_of_2 = true;
}
// Condition if multiple of 2
// do not exist
if (multiple_of_2 == false) {
System.out.println("-1");
return;
}
int last_val = s.charAt(s.length() - 1)- '0';
int second_last_val = s.charAt(s.length() - 2)- '0';
// Condition for zero swaps
// means the number is already
// is divisible by 60
if (last_val == 0&& second_last_val % 2 == 0)
System.out.println(0);
// Condition for only one swap
else if ((last_val == 0
&& second_last_val % 2 != 0)
|| (last_val % 2 == 0
&& second_last_val == 0))
System.out.println(1);
else if (more_zero == true
&& (last_val == 0
&& second_last_val % 2 != 0))
System.out.println(1) ;
// Otherwise 2 swaps required
else
System.out.println(2) ;
}
// Driver Code
public static void main (String[] args)
{
String N = "20";
MinimumSwapOperations(N);
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 program to find minimum number
# of swap operations required
# Function that print minimum number
# of swap operations required
def MinimumSwapOperations(s):
zero_exist = False
multiple_of_2 = False
sum = 0
index_of_zero = 0
more_zero = False
for i in range(len(s)):
val = ord(s[i]) - ord('0')
# Condition if more than one
# zero exist
if (zero_exist == True):
more_zero = True
# Condition if zero_exist
if (val == 0):
zero_exist = True
index_of_zero = i
# Computing total sum of all digits
sum += val
# Condition if zero does not exist or
# the sum is not divisible by 3
if (zero_exist == False or sum % 3 != 0):
print("-1")
return
for i in range(len(s)):
val = ord(s[i]) - ord('0')
# Condition to find a digit that is
# multiple of 2 other than one zero
if (val % 2 == 0 and i != index_of_zero):
multiple_of_2 = True
# Condition if multiple of 2
# do not exist
if (multiple_of_2 == False):
print("-1")
return
last_val = ord(s[len(s) - 1]) - ord('0')
second_last_val = ord(s[len(s) - 2])- ord('0')
# Condition for zero swaps
# means the number is already
# is divisible by 60
if (last_val == 0
and second_last_val % 2 == 0):
print(0)
# Condition for only one swap
elif ((last_val == 0
and second_last_val % 2 != 0)
or (last_val % 2 == 0
and second_last_val == 0)):
print(1)
elif (more_zero == True
and (last_val == 0
and second_last_val % 2 != 0)):
print(1)
# Otherwise 2 swaps required
else:
print(2)
# Driver Code
if __name__ == '__main__':
N = "20"
MinimumSwapOperations(N)
# This code is contributed by mohit kumar 29
C#
// C# program to find minimum number
// of swap operations required
using System;
class GFG {
// Function that print minimum number
// of swap operations required
static void MinimumSwapOperations(string s)
{
bool zero_exist = false;
bool multiple_of_2 = false;
int sum = 0;
int index_of_zero = 0;
bool more_zero = false;
for (int i = 0; i < s.Length; i++) {
int val = s[i] - '0';
// Condition if more than one
// zero exist
if (zero_exist == true)
more_zero = true;
// Condition if zero_exist
if (val == 0) {
zero_exist = true;
index_of_zero = i;
}
// Computing total sum of all digits
sum += val;
}
// Condition if zero does not exist or
// the sum is not divisible by 3
if (zero_exist == false || sum % 3 != 0) {
Console.WriteLine("-1");
return;
}
for (int i = 0; i < s.Length; i++) {
int val = s[i] - '0';
// Condition to find a digit that is
// multiple of 2 other than one zero
if (val % 2 == 0 && i != index_of_zero)
multiple_of_2 = true;
}
// Condition if multiple of 2
// do not exist
if (multiple_of_2 == false) {
Console.WriteLine("-1");
return;
}
int last_val = s[(s.Length - 1)- '0'];
int second_last_val = s[(s.Length - 2)- '0'];
// Condition for zero swaps
// means the number is already
// is divisible by 60
if (last_val == 0&& second_last_val % 2 == 0)
Console.WriteLine(0);
// Condition for only one swap
else if ((last_val == 0
&& second_last_val % 2 != 0)
|| (last_val % 2 == 0
&& second_last_val == 0))
Console.WriteLine(1);
else if (more_zero == true
&& (last_val == 0
&& second_last_val % 2 != 0))
Console.WriteLine(1) ;
// Otherwise 2 swaps required
else
Console.WriteLine(2) ;
}
// Driver Code
public static void Main (string[] args)
{
string N = "20";
MinimumSwapOperations(N);
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript program to find minimum number
// of swap operations required
// Function that print minimum number
// of swap operations required
function MinimumSwapOperations(s)
{
let zero_exist = false;
let multiple_of_2 = false;
let sum = 0;
let index_of_zero = 0;
let more_zero = false;
for (let i = 0; i < s.length; i++) {
let val = s[i] - '0';
// Condition if more than one
// zero exist
if (zero_exist == true)
more_zero = true;
// Condition if zero_exist
if (val == 0) {
zero_exist = true;
index_of_zero = i;
}
// Computing total sum of all digits
sum += val;
}
// Condition if zero does not exist or
// the sum is not divisible by 3
if (zero_exist == false || sum % 3 != 0) {
document.write("-1");
return;
}
for (let i = 0; i < s.length; i++) {
let val = s[i] - '0';
// Condition to find a digit that is
// multiple of 2 other than one zero
if (val % 2 == 0 && i != index_of_zero)
multiple_of_2 = true;
}
// Condition if multiple of 2
// do not exist
if (multiple_of_2 == false) {
document.write("-1");
return;
}
let last_val = s.charAt[s.length - 1] - '0';
let second_last_val = s[(s.length - 2)]- '0';
// Condition for zero swaps
// means the number is already
// is divisible by 60
if (last_val == 0&& second_last_val % 2 == 0)
document.write(0);
// Condition for only one swap
else if ((last_val == 0
&& second_last_val % 2 != 0)
|| (last_val % 2 == 0
&& second_last_val == 0))
document.write(1);
else if (more_zero == true
&& (last_val == 0
&& second_last_val % 2 != 0))
document.write(1) ;
// Otherwise 2 swaps required
else
document.write(2) ;
}
// Driver Code
let N = "20";
MinimumSwapOperations(N);
</script>
Producción:
-1
Complejidad del tiempo: O(N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por nitinkr8991 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA