Dado un número entero N , la tarea es verificar si los elementos del rango [1, N] se pueden dividir en tres subconjuntos de suma igual no vacíos. Si es posible , imprima Sí; de lo contrario, imprima No.
Ejemplos:
Entrada: N = 5
Salida: Sí
Los posibles subconjuntos son {1, 4}, {2, 3} y {5}.
(1 + 4) = (2 + 3) = (5)Entrada: N = 3
Salida: No
Planteamiento: Hay dos casos:
- Si N ≤ 3: En este caso, no es posible dividir los elementos en los subconjuntos que satisfacen la condición dada. Por lo tanto, imprima No.
- Si N > 3: En este caso, solo es posible cuando la suma de todos los elementos del rango [1, N] es divisible por 3 lo que se puede calcular fácilmente como suma = (N * (N + 1)) / 2 . Ahora, si la suma % 3 = 0 , imprima Sí ; de lo contrario , imprima No.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <iostream> using namespace std; // Function that returns true // if the subsets are possible bool possible(int n) { // If n <= 3 then it is not possible // to divide the elements in three subsets // satisfying the given conditions if (n > 3) { // Sum of all the elements // in the range [1, n] int sum = (n * (n + 1)) / 2; // If the sum is divisible by 3 // then it is possible if (sum % 3 == 0) { return true; } } return false; } // Driver code int main() { int n = 5; if (possible(n)) cout << "Yes"; else cout << "No"; return 0; }
Java
// Java implementation of the approach import java.math.*; class GFG { // Function that returns true // if the subsets are possible public static boolean possible(int n) { // If n <= 3 then it is not possible // to divide the elements in three subsets // satisfying the given conditions if (n > 3) { // Sum of all the elements // in the range [1, n] int sum = (n * (n + 1)) / 2; // If the sum is divisible by 3 // then it is possible if (sum % 3 == 0) { return true; } } return false; } // Driver code public static void main(String[] args) { int n = 5; if (possible(n)) System.out.println("Yes"); else System.out.println("No"); } } // This code is contributed by Naman_Garg
Python3
# Python3 implementation of the approach # Function that returns true # if the subsets are possible def possible(n) : # If n <= 3 then it is not possible # to divide the elements in three subsets # satisfying the given conditions if (n > 3) : # Sum of all the elements # in the range [1, n] sum = (n * (n + 1)) // 2; # If the sum is divisible by 3 # then it is possible if (sum % 3 == 0) : return True; return False; # Driver code if __name__ == "__main__" : n = 5; if (possible(n)) : print("Yes"); else : print("No"); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach using System; class GFG { // Function that returns true // if the subsets are possible public static bool possible(int n) { // If n <= 3 then it is not possible // to divide the elements in three subsets // satisfying the given conditions if (n > 3) { // Sum of all the elements // in the range [1, n] int sum = (n * (n + 1)) / 2; // If the sum is divisible by 3 // then it is possible if (sum % 3 == 0) { return true; } } return false; } // Driver code static public void Main () { int n = 5; if (possible(n)) Console.Write("Yes"); else Console.Write("No"); } } // This code is contributed by ajit
Javascript
<script> // Javascript implementation of the approach // Function that returns true // if the subsets are possible function possible(n) { // If n <= 3 then it is not possible // to divide the elements in three subsets // satisfying the given conditions if (n > 3) { // Sum of all the elements // in the range [1, n] let sum = parseInt((n * (n + 1)) / 2); // If the sum is divisible by 3 // then it is possible if (sum % 3 == 0) { return true; } } return false; } // Driver code let n = 5; if (possible(n)) document.write("Yes"); else document.write("No"); // This code is contributed by rishavmahato348 </script>
Producción:
Yes
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Akshita207 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA