Dados N segundos. La tarea es verificar si es posible comenzar desde el reloj de las 12’0 y volver a las 12 solo sumando o restando los segundos dados. Necesitamos usar todos los segundos dados exactamente una vez, podemos agregar un elemento o restarlo.
Ejemplos:
Input: a[] = {60, 60, 120}
Output: YES
Add the first two seconds and
subtract the last one to get back to 0.
Input : a[] = {10, 20, 60, 180}
Output : NO
Enfoque simple: genere todas las combinaciones posibles para resolver el problema anterior. Por lo tanto, genere el conjunto de potencia de N números. Verifique si la suma% de alguien (24 * 60) es igual a cero o no, si lo es, entonces es posible que no lo sea.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if we come back to
// zero or not in a clock
#include <bits/stdc++.h>
using namespace std;
// Function to check all combinations
bool checkCombinations(int a[], int n)
{
// Generate all power sets
int pow_set_size = pow(2, n);
int counter, j;
// Check for every combination
for (counter = 0; counter < pow_set_size; counter++) {
// Store sum for all combinations
int sum = 0;
for (j = 0; j < n; j++) {
/* Check if jth bit in the counter is set
If set then print jth element from set */
if (counter & (1 << j))
sum += a[j]; // if set then consider as '+'
else
sum -= a[j]; // else consider as '-'
}
// If we can get back to 0
if (sum % (24 * 60) == 0)
return true;
}
return false;
}
// Driver Code
int main()
{
int a[] = { 60, 60, 120 };
int n = sizeof(a) / sizeof(a[0]);
if (checkCombinations(a, n))
cout << "YES";
else
cout << "NO";
return 0;
}
Java
// Java program to check if we come
// back to zero or not in a clock
import java.lang.Math;
class GfG
{
// Function to check all combinations
static boolean checkCombinations(int a[], int n)
{
// Generate all power sets
int pow_set_size = (int)Math.pow(2, n);
int counter, j;
// Check for every combination
for (counter = 0; counter < pow_set_size; counter++)
{
// Store sum for all combinations
int sum = 0;
for (j = 0; j < n; j++)
{
/* Check if jth bit in the counter is set
If set then print jth element from set */
if ((counter & (1 << j)) != 0)
sum += a[j]; // if set then consider as '+'
else
sum -= a[j]; // else consider as '-'
}
// If we can get back to 0
if (sum % (24 * 60) == 0)
return true;
}
return false;
}
// Driver code
public static void main(String []args)
{
int a[] = { 60, 60, 120 };
int n = a.length;
if (checkCombinations(a, n))
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code is contributed by Rituraj Jain
Python 3
# Python 3 program to check if we come
# back to zero or not in a clock
# Function to check all combinations
def checkCombinations(a, n):
# Generate all power sets
pow_set_size = pow(2, n)
# Check for every combination
for counter in range(pow_set_size):
# Store sum for all combinations
sum = 0
for j in range(n) :
# Check if jth bit in the counter is set
# If set then print jth element from set
if (counter & (1 << j)):
sum += a[j] # if set then consider as '+'
else:
sum -= a[j] # else consider as '-'
# If we can get back to 0
if (sum % (24 * 60) == 0):
return True
return False
# Driver Code
if __name__ == "__main__":
a = [ 60, 60, 120 ]
n = len(a)
if (checkCombinations(a, n)):
print("YES")
else:
print("NO")
# This code is contributed by ita_c
C#
// C# program to check if we come
// back to zero or not in a clock
using System;
class GfG
{
// Function to check all combinations
static bool checkCombinations(int [] a, int n)
{
// Generate all power sets
int pow_set_size = (int)Math.Pow(2, n);
int counter, j;
// Check for every combination
for (counter = 0; counter < pow_set_size; counter++)
{
// Store sum for all combinations
int sum = 0;
for (j = 0; j < n; j++)
{
/* Check if jth bit in the counter is set
If set then print jth element from set */
if ((counter & (1 << j)) != 0)
sum += a[j]; // if set then consider as '+'
else
sum -= a[j]; // else consider as '-'
}
// If we can get back to 0
if (sum % (24 * 60) == 0)
return true;
}
return false;
}
// Driver code
public static void Main()
{
int [] a = { 60, 60, 120 };
int n = a.Length;
if (checkCombinations(a, n))
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
// This code is contributed by ihritik
PHP
<?php
// PHP program to check if we come back to
// zero or not in a clock
// Function to check all combinations
function checkCombinations($a, $n)
{
// Generate all power sets
$pow_set_size = pow(2, $n);
// Check for every combination
for ($counter = 0;
$counter < $pow_set_size; $counter++)
{
// Store sum for all combinations
$sum = 0;
for ($j = 0; $j < $n; $j++)
{
/* Check if jth bit in the counter is set
If set then print jth element from set */
if ($counter & (1 << $j))
$sum += $a[$j]; // if set then consider as '+'
else
$sum -= $a[$j]; // else consider as '-'
}
// If we can get back to 0
if ($sum % (24 * 60) == 0)
return true;
}
return false;
}
// Driver Code
$a = array( 60, 60, 120 );
$n = sizeof($a);
if (checkCombinations($a, $n))
echo "YES";
else
echo "NO";
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript program to check if we come
// back to zero or not in a clock
// Function to check all combinations
function checkCombinations(a , n) {
// Generate all power sets
var pow_set_size = parseInt( Math.pow(2, n));
var counter, j;
// Check for every combination
for (counter = 0; counter < pow_set_size; counter++)
{
// Store sum for all combinations
var sum = 0;
for (j = 0; j < n; j++) {
/*
* Check if jth bit in the counter is
set If set then print jth element from set
*/
if ((counter & (1 << j)) != 0)
sum += a[j]; // if set then consider as '+'
else
sum -= a[j]; // else consider as '-'
}
// If we can get back to 0
if (sum % (24 * 60) == 0)
return true;
}
return false;
}
// Driver code
var a = [ 60, 60, 120 ];
var n = a.length;
if (checkCombinations(a, n))
document.write("YES");
else
document.write("NO");
// This code contributed by Rajput-Ji
</script>
Producción:
YES
Complejidad de tiempo: O(N*2 N ), ya que estamos usando un bucle anidado para recorrer 2 N *N veces. Donde N es el número de elementos de la array.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Si observamos más de cerca, podemos notar que este problema es básicamente una variación del problema de partición . Entonces podemos optimizarlo usando Programación Dinámica (Consulte el método 2 del Problema de Partición ).