Encuentre si hay un par con una suma dada en la array ordenada rotada

Dada una array arr[] de distintos elementos de tamaño N que se ordena y luego alrededor de un punto desconocido, la tarea es verificar si la array tiene un par con una suma X dada .

Ejemplos: 

Entrada: arr[] = {11, 15, 6, 8, 9, 10}, X = 16
Salida: verdadero
Explicación: Hay un par (6, 10) con suma 16

Entrada: arr[] = {11, 15, 26, 38, 9, 10}, X = 35
Salida: verdadero
Explicación: Hay un par (26, 9) con suma 35

Entrada: arr[] = {11, 15, 26, 38, 9, 10}, X = 45
Salida: falso
Explicación: No hay par con suma 45.

Hemos discutido una solución O(n) para una array ordenada (Consulte los pasos 2, 3 y 4 del Método 1) en este artículo. También podemos extender esta solución para las arrays rotadas. 

Enfoque: La idea es: 

Primero encuentre el elemento más grande en una 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 los índices de los 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.

Ilustración:

Tomemos un ejemplo arr[]={11, 15, 6, 8, 9, 10} , sum=16 .
pivote = 1,  

l = 2, r = 1:
        => arr[2] + arr[1] = 6 + 15 = 21 que es > 16 
        => Entonces, disminuya r circularmente. r = ( 6 + 1 – 1) % 6, r = 0

l = 2, r = 0:
        => arr[2] + arr[0] = 17 que es > 16. 
        => Entonces, disminuya r circularmente. r = (6 + 0 – 1) % 6, r = 5

l = 2, r = 5:
        => arr[2] + arr[5] = 16 que es igual a 16. 
        => Por lo tanto, devuelve verdadero

Por lo tanto, existe tal par.

Siga los pasos mencionados a continuación para implementar la idea:

• Ejecutaremos un bucle for de 0 a N-1 para encontrar el punto  de pivote .
• Establezca el puntero izquierdo (l) en el valor más pequeño y el puntero derecho (r) en el valor más alto.
• Para restringir el movimiento circular dentro de la array, aplicaremos la operación de módulo por el tamaño de la array.
• mientras yo! = r , seguiremos comprobando si arr[l] + arr[r] = sum .
  • Si arr[l] + arr[r] es mayor que X, actualice r = (N+r-1) % N .
  • Si arr[l] + arr[r] es menor que X, actualice l = (l+1) % N .
  • Si arr[l] + arr[r] es igual al valor X, entonces devuelve verdadero.
• Si no se encuentra dicho par después de completar la iteración, devuelve falso.

A continuación se muestra la implementación del enfoque anterior. 

// C++ code to implement the approach
  
#include <bits/stdc++.h>
using namespace std;
  
// This function returns true if arr[0..n-1]
// has a pair with sum equals to x.
bool pairInSortedRotated(int arr[], int n, int x)
{
    // Find the pivot element
    int i;
    for (i = 0; i < n - 1; i++)
        if (arr[i] > arr[i + 1])
            break;
  
    // l is now index of smallest element
    int l = (i + 1) % n;
  
    // r is now index of largest element
    int r = i;
  
    // Keep moving either l or r till they meet
    while (l != r) {
  
        // If we find a pair with sum x,
        // we return true
        if (arr[l] + arr[r] == x)
            return true;
  
        // If current pair sum is less,
        // move to the higher sum
        if (arr[l] + arr[r] < x)
            l = (l + 1) % n;
  
        // Move to the lower sum side
        else
            r = (n + r - 1) % n;
    }
    return false;
}
  
// Driver code
int main()
{
    int arr[] = { 11, 15, 6, 8, 9, 10 };
    int X = 16;
    int N = sizeof(arr) / sizeof(arr[0]);
  
    // Function call
    if (pairInSortedRotated(arr, N, X))
        cout << "true";
    else
        cout << "false";
  
    return 0;
}

// Java program to find a pair with a given
// sum in a sorted and rotated array
class PairInSortedRotated {
    // This function returns true if arr[0..n-1]
    // has a pair with sum equals to x.
    static boolean pairInSortedRotated(int arr[], int n,
                                       int x)
    {
        // Find the pivot element
        int i;
        for (i = 0; i < n - 1; i++)
            if (arr[i] > arr[i + 1])
                break;
  
        // l is now index of smallest element
        int l = (i + 1) % n;
  
        // r is now index of largest element
        int r = i;
  
        // Keep moving either l or r till they meet
        while (l != r) {
            // If we find a pair with sum x, we
            // return true
            if (arr[l] + arr[r] == x)
                return true;
  
            // If current pair sum is less, move
            // to the higher sum
            if (arr[l] + arr[r] < x)
                l = (l + 1) % n;
  
            // Move to the lower sum side
            else
                r = (n + r - 1) % n;
        }
        return false;
    }
  
    /* Driver program to test above function */
    public static void main(String[] args)
    {
        int arr[] = { 11, 15, 6, 8, 9, 10 };
        int X = 16;
        int N = arr.length;
  
        if (pairInSortedRotated(arr, N, X))
            System.out.print("true");
        else
            System.out.print("false");
    }
}
/*This code is contributed by Prakriti Gupta*/

# Python3 program to find a
# pair with a given sum in
# a sorted and rotated array
  
  
# This function returns True
# if arr[0..n-1] has a pair
# with sum equals to x.
def pairInSortedRotated(arr, n, x):
  
    # Find the pivot element
    for i in range(0, n - 1):
        if (arr[i] > arr[i + 1]):
            break
  
    # l is now index of smallest element
    l = (i + 1) % n
    # r is now index of largest element
    r = i
  
    # Keep moving either l
    # or r till they meet
    while (l != r):
  
        # If we find a pair with
        # sum x, we return True
        if (arr[l] + arr[r] == x):
            return True
  
        # If current pair sum is less,
        # move to the higher sum
        if (arr[l] + arr[r] < x):
            l = (l + 1) % n
        else:
  
            # Move to the lower sum side
            r = (n + r - 1) % n
  
    return False
  
  
# Driver program to test above function
arr = [11, 15, 6, 8, 9, 10]
X = 16
N = len(arr)
  
if (pairInSortedRotated(arr, N, X)):
    print("true")
else:
    print("false")
  
  
# This article contributed by saloni1297

// C# program to find a pair with a given
// sum in a sorted and rotated array
using System;
  
class PairInSortedRotated {
    // This function returns true if arr[0..n-1]
    // has a pair with sum equals to x.
    static bool pairInSortedRotated(int[] arr, int n, int x)
    {
        // Find the pivot element
        int i;
        for (i = 0; i < n - 1; i++)
            if (arr[i] > arr[i + 1])
                break;
  
        // l is now index of smallest element
        int l = (i + 1) % n;
  
        // r is now index of largest element
        int r = i;
  
        // Keep moving either l or r till they meet
        while (l != r) {
            // If we find a pair with sum x, we
            // return true
            if (arr[l] + arr[r] == x)
                return true;
  
            // If current pair sum is less,
            // move to the higher sum
            if (arr[l] + arr[r] < x)
                l = (l + 1) % n;
  
            // Move to the lower sum side
            else
                r = (n + r - 1) % n;
        }
        return false;
    }
  
    // Driver Code
    public static void Main()
    {
        int[] arr = { 11, 15, 6, 8, 9, 10 };
        int X = 16;
        int N = arr.Length;
  
        if (pairInSortedRotated(arr, N, X))
            Console.WriteLine("true");
        else
            Console.WriteLine("false");
    }
}
  
// This code is contributed by vt_m.

<?php
// PHP program to find a pair
// with a given sum in a
// sorted and rotated array
  
// This function returns true
// if arr[0..n-1] has a pair 
// with sum equals to x.
  
function pairInSortedRotated($arr, $n, $x)
{
    // Find the pivot element
    $i;
    for ($i = 0; $i < $n - 1; $i++)
        if ($arr[$i] > $arr[$i + 1])
            break;
          
    // l is now index of 
    // smallest element
    $l = ($i + 1) % $n; 
      
    // r is now index of
    // largest element
    $r = $i;
  
    // Keep moving either l 
    // or r till they meet
    while ($l != $r)
    {
        // If we find a pair with
        // sum x, we return true
        if ($arr[$l] + $arr[$r] == $x)
            return true;
  
        // If current pair sum is 
        // less, move to the higher sum
        if ($arr[$l] + $arr[$r] < $x)
            $l = ($l + 1) % $n;
              
        // Move to the lower sum side
        else 
            $r = ($n + $r - 1) % $n;
    }
    return false;
}
  
// Driver Code
$arr = array(11, 15, 6, 8, 9, 10);
$X = 16;
$N = sizeof($arr);
  
if (pairInSortedRotated($arr, $N, $X))
    echo "true";
else
    echo "false";
  
// This code is contributed by aj_36
?>

<script>
  
// Javascript program to find a 
// pair with a given sum in a 
// sorted and rotated array
      
// This function returns true if arr[0..n-1] 
// has a pair with sum equals to x.
function pairInSortedRotated(arr, n, x)
{
      
    // Find the pivot element
    let i;
    for(i = 0; i < n - 1; i++)
        if (arr[i] > arr[i + 1])
            break;
              
    // l is now index of                                          
    // smallest element          
    let l = (i + 1) % n; 
      
    // r is now index of largest 
    // element                   
    let r = i;       
     
    // Keep moving either l or 
    // r till they meet
    while (l != r)
    {
          
         // If we find a pair with sum x, we
         // return true
         if (arr[l] + arr[r] == x)
              return true;
     
         // If current pair sum is less, move 
         // to the higher sum
         if (arr[l] + arr[r] < x)
              l = (l + 1) % n;
                
         // Move to the lower sum side       
         else  
              r = (n + r - 1) % n;
    }
    return false;
}
  
// Driver code
let arr = [ 11, 15, 6, 8, 9, 10 ];
let X = 16;
let N = arr.length;
  
if (pairInSortedRotated(arr, N, X))
    document.write("true");
else
    document.write("false");
  
// This code is contributed by avanitrachhadiya2155
      
</script>

true

Complejidad temporal: 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í .
Espacio Auxiliar: O(1).

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.