Dado un número entero N (N ≠ 0), la tarea es encontrar un rango [L, R] (−10⁻¹⁸ < L < R < 10¹⁸) tal que la suma de todos los números enteros en este rango sea igual a N .
L + (L+1) + … + (R−1) + R = norte
Ejemplos:
Entrada: N = 3
Salida: -2 3
Explicación: Para L = -2 y R = -3 la suma se convierte en -2 + (-1) + 0 + 1 + 2 + 3 = 3Entrada: N = -6
Salida: -6 5
Explicación: La suma de este rango [-6, 5] es -6 + (-5) + (-4) + (-3) + (-2) + (- 1) + 0 + 1+ 2 + 3 + 4 + 5 = -6
Enfoque ingenuo: para cada valor de L, intente encontrar un valor R que satisfaga la condición L + (L+1) + . . . + (R-1) + R = N, usando bucle anidado.
Tiempo Complejidad: O(N 2 )
Espacio auxiliar: O(1)
Enfoque eficiente: dado que L y R son números enteros y también pueden ser números negativos, el problema anterior se puede resolver en O (1) de manera eficiente. Considere la siguiente observación:
- Para que N sea un entero positivo podemos considerar:
[−(N – 1)] + [−(N – 2)] + . . . -1 + 0 + 1 + . . . + (norte – 1) + norte =
-(norte – 1) + (norte – 1) – (norte – 2) + (norte – 2) + . . . + 1 – 1 + 0 + N = N
Entonces, L = -(N – 1) y R = N
- De manera similar , para que N sea negativo , podemos considerar:
norte + (norte + 1) + . . . -1 + 0 + 1 + . . . + [-(N + 2)] + [-(N + 1)] =
(N + 1) – (N + 1) + (N + 2) – (N + 2) + . . . -1 + 1 + 0 + N = N
Entonces L = N y R = -(N + 1)
Por lo tanto, la solución a este problema en complejidad por unidad de tiempo es:
L = -(N – 1) y R = N, cuando N es un número entero positivo.
L = N y R = -(N + 1), cuando N es un número entero negativo.
Nota: Este es el rango más largo posible (es decir, R – L tiene el valor más alto) que satisface el requisito del problema.
A continuación se muestra la implementación del enfoque:
C++
// C++ code to implement above approach #include <bits/stdc++.h> using namespace std; // Function to find two integers void Find_Two_Intergers(long long int N) { // Variable to store value of L and R long long int L, R; // When N is positive if (N > 0) { L = -(N - 1); R = N; } // When N is negative else { L = N; R = -(N + 1); } cout << L << " " << R; } // Driver Code int main() { long long int N = 3; Find_Two_Integers(N); return 0; }
C
// C code to implement above approach #include <stdio.h> // Function to find two integers void Find_Two_Intergers(long long int N) { // Variable to store L and R long long int L, R; // When N is positive if (N > 0) { L = -(N - 1); R = N; } // When N is negative else { L = N; R = -(N + 1); } printf("%lld %lld", L, R); } // Driver code int main() { long long int N = 3; Find_Two_Integers(N); return 0; }
Java
// Java code for the above approach import java.io.*; class GFG { // Function to find two integers static void Find_Two_Intergers(long N) { // Variable to store value of L and R long L, R; // When N is positive if (N > 0) { L = -(N - 1); R = N; } // When N is negative else { L = N; R = -(N + 1); } System.out.print( L + " " + R); } // Driver Code public static void main (String[] args) { long N = 3; Find_Two_Integers(N); } } // This code is contributed by Potta Lokesh
Python3
# Python code to implement above approach # Function to find two integers def Find_Two_Intergers(N): # variable to store L and R L = 0 R = 0 # When N is positive if N > 0: L = -(N-1) R = N # When N is negative else: L = N R = -(N+1) print(L, R) # Driver code N = 3 Find_Two_Integers(N)
C#
// C# code for the above approach using System; class GFG { // Function to find two integers static void Find_Two_Intergers(long N) { // Variable to store value of L and R long L, R; // When N is positive if (N > 0) { L = -(N - 1); R = N; } // When N is negative else { L = N; R = -(N + 1); } Console.Write( L + " " + R); } // Driver Code public static void Main (String[] args) { long N = 3; Find_Two_Integers(N); } } // This code is contributed by Saurabh Jaiswal
Javascript
<script> // Javascript code to implement above approach // Function to find two integers function Find_Two_Intergers(N) { // Variable to store value of L and R let L, R; // When N is positive if (N > 0) { L = -(N - 1); R = N; } // When N is negative else { L = N; R = -(N + 1); } document.write(L + " " + R); } // Driver Code let N = 3; Find_Two_Integers(N); // This code is contributed by gfgking. </script>
-2 3
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por hrithik2108 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA