Programa C++ para Dada una array ordenada y rotada, encuentre si hay un par con una suma dada

Dada una array que se ordena y luego se gira alrededor de un punto desconocido. Encuentra si la array tiene un par con una suma dada ‘x’. Se puede suponer que todos los elementos de la array son distintos.

Ejemplos: 

Input: arr[] = {11, 15, 6, 8, 9, 10}, x = 16
Output: true
There is a pair (6, 10) with sum 16

Input: arr[] = {11, 15, 26, 38, 9, 10}, x = 35
Output: true
There is a pair (26, 9) with sum 35

Input: arr[] = {11, 15, 26, 38, 9, 10}, x = 45
Output: false
There is no pair with sum 45.

Hemos discutido una solución O(n) para una array ordenada (Consulte los pasos 2, 3 y 4 del Método 1) . También podemos extender esta solución para una array rotada. La idea es encontrar primero el elemento más grande en la array, que también es el punto de pivote, y el elemento justo después del más grande es el elemento más pequeño. Una vez que tenemos índices de elementos más grandes y más pequeños, usamos un algoritmo similar de encuentro en el medio (como se discutió aquí en el método 1 ) para encontrar si hay un par. Lo único nuevo aquí es que los índices se incrementan y decrementan de manera rotacional usando aritmética modular.

A continuación se muestra la implementación de la idea anterior.  

Producción : 

Array has two elements with sum 16

La complejidad temporal de la solución anterior es O(n). El paso para encontrar el pivote se puede optimizar a O (Iniciar sesión) utilizando el enfoque de búsqueda binaria que se analiza aquí .

¿Cómo contar todos los pares que tienen suma x?  
El algoritmo paso a paso es:  

1. Encuentre el elemento pivote de la array ordenada y rotada. El elemento pivote es el elemento más grande de la array. El elemento más pequeño estará adyacente a él.
2. Use dos punteros (digamos, izquierdo y derecho) con el puntero izquierdo apuntando al elemento más pequeño y el puntero derecho apuntando al elemento más grande.
3. Encuentre la suma de los elementos señalados por ambos punteros.
4. Si la suma es igual a x, entonces incremente el conteo. Si la suma es menor que x, entonces, para aumentar la suma, mueva el puntero izquierdo a la siguiente posición incrementándolo de forma rotatoria. Si la suma es mayor que x, entonces para disminuir la suma, mueva el puntero derecho a la siguiente posición al disminuirlo de manera rotacional.
5. Repita los pasos 3 y 4 hasta que el puntero izquierdo no sea igual al puntero derecho o hasta que el puntero izquierdo no sea igual al puntero derecho – 1.
6. Imprime el conteo final.

A continuación se muestra la implementación del algoritmo anterior: 

// C++ program to find number of pairs with 
// a given sum in a sorted and rotated array.
#include<bits/stdc++.h>
using namespace std;
  
// This function returns count of number of pairs
// with sum equals to x.
int pairsInSortedRotated(int arr[], int n, int x)
{
    // Find the pivot element. Pivot element
    // is largest element of array.
    int i;
    for (i = 0; i < n-1; i++)
        if (arr[i] > arr[i+1])
            break;
      
    // l is index of smallest element.
    int l = (i + 1) % n; 
      
    // r is index of largest element.
    int r = i;
      
    // Variable to store count of number
    // of pairs.
    int cnt = 0;
  
    // Find sum of pair formed by arr[l] and
    // and arr[r] and update l, r and cnt 
    // accordingly.
    while (l != r)
    {
        // If we find a pair with sum x, then 
        // increment cnt, move l and r to 
        // next element.
        if (arr[l] + arr[r] == x){
            cnt++;
              
            // This condition is required to 
            // be checked, otherwise l and r
            // will cross each other and loop
            // will never terminate.
            if(l == (r - 1 + n) % n){
                return cnt;
            }
              
            l = (l + 1) % n;
            r = (r - 1 + n) % n;
        }
  
        // If current pair sum is less, move to 
        // the higher sum side.
        else if (arr[l] + arr[r] < x)
            l = (l + 1) % n;
          
        // If current pair sum is greater, move 
        // to the lower sum side.
        else 
            r = (n + r - 1)%n;
    }
      
    return cnt;
}
  
/* Driver program to test above function */
int main()
{
    int arr[] = {11, 15, 6, 7, 9, 10};
    int sum = 16;
    int n = sizeof(arr)/sizeof(arr[0]);
  
    cout << pairsInSortedRotated(arr, n, sum);
      
    return 0;
} 

Producción: 

2

Complejidad de tiempo: O(n) 
Espacio auxiliar: O(1)  Nikhil Jindal
sugiere este método .
 

Ejercicio: 
1) Amplíe la solución anterior para trabajar con arreglos con duplicados permitidos.
Este artículo es una contribución de Himanshu Gupta . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Consulte el artículo completo sobre Dada una array ordenada y rotada, busque si hay un par con una suma dada para obtener más detalles.