Dada una array arr[] de distintos elementos de tamaño N que se ordena y luego alrededor de un punto desconocido, la tarea es contar el número de pares en la array que tienen una suma X dada .
Ejemplos:
Entrada: arr[] = {11, 15, 26, 38, 9, 10}, X = 35
Salida: 1
Explicación: Hay un par (26, 9) con suma 35Entrada: arr[] = {11, 15, 6, 7, 9, 10}, X = 16
Salida: 2
Enfoque: La idea es similar a lo que se menciona a continuación.
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 explica aquí en el método 1 ) para contar el número de pares que suman X. Los índices se incrementan y decrementan de forma rotativa usando aritmética modular.
Siga la siguiente ilustración para una mejor comprensión.
Ilustración:
Tomemos un ejemplo arr[]={11, 15, 6, 7, 9, 10} , X = 16, count=0;
Inicialmente pivote = 1,l = 2, r = 1:
=> arr[2] + arr[1] = 6 + 15 = 21, que es > 16
=> Decrementar r = ( 6 + 1 – 1) % 6, r = 0l = 2, r = 0:
=> arr[2] + arr[0] = 17 que es > 16,
=> Decrementar r = (6 + 0 – 1) % 6, r = 5l = 2, r = 5:
=> arr[2] + arr[5] = 16 que es igual a 16,
=> Por lo tanto contar = 1 y
=> Decement r = (6 + 5 – 1) % 6, r = 4 e incremento l = (2 + 1) % 6, l = 3l = 3, r = 4:
=> arr[3] + arr[4] = 16
=> Por lo tanto, incrementa la cuenta. Entonces cuenta = 2
=> Entonces decrementa r = (6 + 4 – 1) % 6, r = 3 e incrementa l = 4l = 4, r = 3:
=> l > r. Así que rompe el bucle.Entonces obtenemos cuenta = 2
Siga los siguientes pasos 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, aplique la operación de módulo por el tamaño de la array.
- mientras yo! = r , sigue comprobando si arr[l] + arr[r] = sum.
- Si arr[l] + arr[r] > sum , actualice r=(N+r-1) % N .
- Si arr[l] + arr[r] < sum , actualice l=(l+1) % N .
- Si arr[l] + arr[r] = sum , incrementa la cuenta. También incremente l y disminuya r .
A continuación se muestra la implementación de la idea anterior.
C++
// 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 X = 16;
int N = sizeof(arr) / sizeof(arr[0]);
cout << pairsInSortedRotated(arr, N, X);
return 0;
}
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 X = 16;
int N = arr.length;
System.out.println(pairsInSortedRotated(arr, N, X));
}
}
// This code is contributed by ajit
Python3
# Python program to find # number of pairs with # a given sum in a sorted # and rotated array. # This function returns # count of number of pairs # with sum equals to x. def pairsInSortedRotated(arr, n, x): # Find the pivot element. # Pivot element is largest # element of array. for i in range(n): if arr[i] > arr[i + 1]: break # l is index of # smallest element. l = (i + 1) % n # r is index of # largest element. r = i # Variable to store # count of number # of pairs. 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 += 1 # 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. elif 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 arr = [11, 15, 6, 7, 9, 10] X = 16 N = len(arr) print(pairsInSortedRotated(arr, N, X)) # This code is contributed by ChitraNayal
C#
// C# program to find
// number of pairs with
// a given sum in a sorted
// and rotated array.
using System;
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
static public void Main()
{
int[] arr = { 11, 15, 6, 7, 9, 10 };
int X = 16;
int N = arr.Length;
Console.WriteLine(
pairsInSortedRotated(arr, N, X));
}
}
// This code is contributed by akt_mit
PHP
<?php
// PHP program to find number
// of pairs with a given sum
// in a sorted and rotated array.
// This function returns count
// of number of pairs with sum
// equals to x.
function pairsInSortedRotated($arr,
$n, $x)
{
// Find the pivot element.
// Pivot element is largest
// element of array.
$i;
for ($i = 0; $i < $n - 1; $i++)
if ($arr[$i] > $arr[$i + 1])
break;
// l is index of
// smallest element.
$l = ($i + 1) % $n;
// r is index of
// largest element.
$r = $i;
// Variable to store
// count of number
// of pairs.
$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
$arr = array(11, 15, 6,
7, 9, 10);
$X = 16;
$N = sizeof($arr) / sizeof($arr[0]);
echo pairsInSortedRotated($arr, $N, $X);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find
// number of pairs with
// a given sum in a sorted
// and rotated array.
// This function returns
// count of number of pairs
// with sum equals to x.
function pairsInSortedRotated(arr, n, x)
{
// Find the pivot element.
// Pivot element is largest
// element of array.
let i;
for (i = 0; i < n - 1; i++)
if (arr[i] > arr[i + 1])
break;
// l is index of
// smallest element.
let l = (i + 1) % n;
// r is index of
// largest element.
let r = i;
// Variable to store
// count of number
// of pairs.
let 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
let arr = [11, 15, 6, 7, 9, 10];
let X = 16;
let N = arr.length;
document.write(pairsInSortedRotated(arr, N, X));
// This code is contributed by rag2127
</script>
Producción
2
Complejidad temporal: O(N). Como estamos realizando operaciones lineales en una array.
Espacio Auxiliar: O(1). Como espacio adicional constante se utiliza.
Este método es sugerido por Nikhil Jindal .
Publicación traducida automáticamente
Artículo escrito por animeshdey y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA