Dado un número entero N , la tarea es contar el número de pares entre los primeros N números naturales, con suma igual a N .
Ejemplos:
Entrada: N = 8
Salida: 3
Explicación:
Todos los pares posibles con suma 8 son {(1, 7), (2, 6), (3, 5)}Entrada: N = 9
Salida: 4
Enfoque ingenuo:
el enfoque más simple para resolver el problema es usar dos punteros . Siga los pasos a continuación para resolver el problema:
- Establezca i = 0 y j = N – 1 inicialmente.
- Iterar hasta i >= j , y para cada par de i, j , comprobar si su suma es igual a N o no. Si es así, aumente el número de pares.
- Pase al siguiente par aumentando y disminuyendo i y j en 1 respectivamente.
- Finalmente, imprima el conteo de pares obtenidos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement // the above approach #include <iostream> using namespace std; int numberOfPairs(int n) { // Stores the count of // pairs int count = 0; // Set the two pointers int i = 1, j = n - 1; while (i < j) { // Check if the sum of // pairs is equal to N if (i + j == n) { // Increase the count // of pairs count++; } // Move to the next pair i++; j--; } return count; } // Driver Code int main() { int n = 8; cout << numberOfPairs(n); return 0; }
Java
// Java program for the above approach import java.io.*; class GFG{ // Function to calculate the value of count public static int numberOfPairs(int n) { // Stores the count of pairs int count = 0; // Set the two pointers int i = 1, j = n - 1; while (i < j) { // Check if the sum of // pairs is equal to N if (i + j == n) { // Increase the count // of pairs count++; } // Move to the next pair i++; j--; } return count; } // Driver code public static void main (String[] args) { int n = 8; System.out.println(numberOfPairs(n)); } } // This code is contributed by piyush3010
Python3
# Python3 program for the # above approach def numberOfPairs(n): # Stores the count # of pairs count = 0 # Set the two pointers i = 1 j = n - 1 while(i < j): # Check if the sum # of pirs is equal to n if (i + j) == n: # Increase the count of pairs count += 1 # Move to the next pair i += 1 j -= 1 return count # Driver code if __name__=='__main__': n = 8 print(numberOfPairs(n)) # This code is contributed by virusbuddah_
C#
// C# program for the above approach using System; class GFG{ // Function to calculate the value of count public static int numberOfPairs(int n) { // Stores the count of pairs int count = 0; // Set the two pointers int i = 1, j = n - 1; while (i < j) { // Check if the sum of // pairs is equal to N if (i + j == n) { // Increase the count // of pairs count++; } // Move to the next pair i++; j--; } return count; } // Driver code public static void Main (string[] args) { int n = 8; Console.Write(numberOfPairs(n)); } } // This code is contributed by rock_cool
Javascript
<script> // Javascript program to implement // the above approach function numberOfPairs(n) { // Stores the count of // pairs let count = 0; // Set the two pointers let i = 1, j = n - 1; while (i < j) { // Check if the sum of // pairs is equal to N if (i + j == n) { // Increase the count // of pairs count++; } // Move to the next pair i++; j--; } return count; } // Driver code let n = 8; document.write(numberOfPairs(n)); // This code is contributed by divyesh072019 </script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente:
para optimizar el enfoque anterior, solo necesitamos observar si N es par o impar. Si N es par, la cuenta de pares posibles es N/2 – 1. De lo contrario, es N/2.
Ilustración:
N = 8
Todos los pares posibles son (1, 7), (2, 6) y (3, 5)
Por lo tanto, cuenta de pares posibles = 3 = 8/2 – 1N = 9
Todos los pares posibles son (1, 8), (2, 7), (3, 6) y (4, 5)
Por lo tanto, cuenta de pares posibles = 4 = 9/2
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count the number // of pairs among the first N // natural numbers with sum N #include <iostream> using namespace std; // Function to return the // count of pairs int numberOfPairs(int n) { // If n is even if (n % 2 == 0) // Count of pairs return n / 2 - 1; // Otherwise else return n / 2; } // Driver Code int main() { int n = 8; cout << numberOfPairs(n); return 0; }
Java
// Java program to count the number // of pairs among the first N // natural numbers with sum N import java.io.*; class GFG{ // Function to calculate the value of count public static int numberOfPairs(int n) { // If n is even if (n % 2 == 0) // Count of pairs return n / 2 - 1; // Otherwise else return n / 2; } // Driver code public static void main (String[] args) { int n = 8; System.out.println(numberOfPairs(n)); } } // This code is contributed by piyush3010
Python3
# Python3 program to count the number # of pairs among the first N # natural numbers with sum N # Function to calculate the value of count def numberOfPairs(n): # If n is even if (n % 2 == 0): # Count of pairs return n // 2 - 1; # Otherwise else: return n // 2; # Driver code n = 8; print(numberOfPairs(n)); # This code is contributed by Rajput-Ji
C#
// C# program to count the number // of pairs among the first N // natural numbers with sum N using System; class GFG{ // Function to calculate the value of count public static int numberOfPairs(int n) { // If n is even if (n % 2 == 0) // Count of pairs return n / 2 - 1; // Otherwise else return n / 2; } // Driver code public static void Main (string[] args) { int n = 8; Console.Write(numberOfPairs(n)); } } // This code is contributed by Ritik Bansal
Javascript
<script> // Javascript program to count the number // of pairs among the first N // natural numbers with sum N // Function to return the // count of pairs function numberOfPairs(n) { // If n is even if (n % 2 == 0) // Count of pairs return (n / 2 - 1); // Otherwise else return (n / 2); } // Driver code let n = 8; document.write(numberOfPairs(n)); // This code is contributed by rameshtravel07 </script>
3
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por mishrapriyanshu557 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA