Encuentre el rango [L, R] tal que la suma de los números en este rango sea igual a N

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 = 3

Entrada: 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>
Producción

-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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *