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.
Java
// 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;
int l = (i + 1) % n; // l is now index of
// smallest element
int r = i; // r is now index of largest
//element
// 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 */
public static void main (String[] args)
{
int arr[] = {11, 15, 6, 8, 9, 10};
int sum = 16;
int n = arr.length;
if (pairInSortedRotated(arr, n, sum))
System.out.print("Array has two elements" +
" with sum 16");
else
System.out.print("Array doesn't have two" +
" elements with sum 16 ");
}
}
/*This code is contributed by Prakriti Gupta*/
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:
- 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.
- 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.
- Encuentre la suma de los elementos señalados por ambos punteros.
- 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.
- 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.
- Imprime el conteo final.
A continuación se muestra la implementación del algoritmo anterior:
Java
// Java program to find
// number of pairs with
// a given sum in a sorted
// and rotated array.
import java.io.*;
class GFG
{
// This function returns
// count of number of pairs
// with sum equals to x.
static 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 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 Code
public static void main (String[] args)
{
int arr[] = {11, 15, 6, 7, 9, 10};
int sum = 16;
int n = arr.length;
System.out.println(
pairsInSortedRotated(arr, n, sum));
}
}
// This code is contributed by ajit
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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA