Find a pair with the given difference

Last Updated : 28 Dec, 2023

Given an unsorted array and a number n, find if there exists a pair of elements in the array whose difference is n.
Examples:

Input: arr[] = {5, 20, 3, 2, 50, 80}, n = 78
Output: Pair Found: (2, 80)

Input: arr[] = {90, 70, 20, 80, 50}, n = 45
Output: No Such Pair

Method 1: The simplest method is to run two loops, the outer loop picks the first element (smaller element) and the inner loop looks for the element picked by outer loop plus n. Time complexity of this method is O(n²).

Algorithm:

Start iterating through each element of the array using an outer loop.
For each element, start iterating again through each of the elements of the array except the one picked in outer loop using an inner loop.
If the difference between the current element and any of the elements of it is equal to the given difference, print both elements.
Continue the process until all possible pairs of elements are compared.
If no pair found, print “No such pair”.

Below is the implementation of the approach:

C++

// C++ code for the approach
 
#include<bits/stdc++.h>
using namespace std;
 
// Function to find if there exists a pair 
// of elements in the array whose difference is n
void findPair(int arr[], int n, int diff) {
    // Nested loop to compare all possible 
      // pairs of elements
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
              if(i == j)
                  continue;
           
            // If the difference between the 
              // two elements is n, print them
            if((arr[j] - arr[i]) == diff) {
                cout << "Pair Found: (" << arr[i] << ", " << arr[j] << ")";
                  return;
            }
        }
    }
   
      cout << "No such pair";
}
 
int main() {
      // Input array and diff
    int arr[] = { 1, 8, 30, 40, 100 };
    int n = sizeof(arr)/sizeof(arr[0]);
    int diff = -60;
       
      // Function call
    findPair(arr, n, diff);
    return 0;
}

Java

import java.util.Arrays;
 
public class FindPairWithDifference {
     
    // Function to find if there exists a pair
    // of elements in the array whose difference is n
    static void findPair(int[] arr, int n, int diff) {
        // Nested loop to compare all possible
        // pairs of elements
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j)
                    continue;
 
                // If the difference between the
                // two elements is n, print them
                if ((arr[j] - arr[i]) == diff) {
                    System.out.println("Pair Found: (" + arr[i] + ", " + arr[j] + ")");
                    return;
                }
            }
        }
 
        System.out.println("No such pair");
    }
 
    public static void main(String[] args) {
        // Input array and diff
        int[] arr = { 1, 8, 30, 40, 100 };
        int n = arr.length;
        int diff = -60;
 
        // Function call
        findPair(arr, n, diff);
    }
}

Python3

# Function to find if there exists a pair
# of elements in the array whose difference is n
def find_pair(arr, n, diff):
    # Nested loop to compare all possible
    # pairs of elements
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
             
            # If the difference between the
            # two elements is n, print them
            if arr[j] - arr[i] == diff:
                print(f"Pair Found: ({arr[i]}, {arr[j]})")
                return
     
    print("No such pair")
 
# Input array and diff
arr = [1, 8, 30, 40, 100]
n = len(arr)
diff = -60
 
# Function call
find_pair(arr, n, diff)

C#

using System;
 
class MainClass {
    // Function to find if there exists a pair 
    // of elements in the array whose difference is n
    static void FindPair(int[] arr, int n, int diff) {
        // Nested loop to compare all possible pairs of elements
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j)
                    continue;
 
                // If the difference between the two elements is n, print them
                if ((arr[j] - arr[i]) == diff) {
                    Console.WriteLine($"Pair Found: ({arr[i]}, {arr[j]})");
                    return;
                }
            }
        }
 
        Console.WriteLine("No such pair");
    }
 
    public static void Main (string[] args) {
        // Input array and diff
        int[] arr = { 1, 8, 30, 40, 100 };
        int n = arr.Length;
        int diff = -60;
 
        // Function call
        FindPair(arr, n, diff);
    }
}

Javascript

function findPair(arr, diff) {
  // Nested loop to compare 
  // all  possible pairs of elements
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i === j) {
        continue;
      }
      // If the difference between the two elements is 'diff' 
      // print them and return
      if (arr[j] - arr[i] === diff) {
        console.log(`Pair Found: (${arr[i]}, ${arr[j]})`);
        return;
      }
    }
  }
  console.log('No such pair');
}
 
// Input array and 'diff'
const arr = [1, 8, 30, 40, 100];
const diff = -60;
// Function call
findPair(arr, diff);

Output

Pair Found: (100, 40)

Time Complexity: O(n*n) as two nested for loops are executing both from 1 to n where n is size of input array.
Space Complexity: O(1) as no extra space has been taken.

Method 2: We can use sorting and Binary Search to improve time complexity to O(nLogn). The first step is to sort the array in ascending order. Once the array is sorted, traverse the array from left to right, and for each element arr[i], binary search for arr[i] + n in arr[i+1..n-1]. If the element is found, return the pair. Both first and second steps take O(nLogn). So overall complexity is O(nLogn).
Method 3: The second step of the Method -2 can be improved to O(n). The first step remains the same. The idea for the second step is to take two index variables i and j, and initialize them as 0 and 1 respectively. Now run a linear loop. If arr[j] – arr[i] is smaller than n, we need to look for greater arr[j], so increment j. If arr[j] – arr[i] is greater than n, we need to look for greater arr[i], so increment i. Thanks to Aashish Barnwal for suggesting this approach.
The following code is only for the second step of the algorithm, it assumes that the array is already sorted.

C++

// C++ program to find a pair with the given difference 
#include <bits/stdc++.h>
using namespace std;
 
// The function assumes that the array is sorted 
bool findPair(int arr[], int size, int n) 
{ 
    // Initialize positions of two elements 
    int i = 0; 
    int j = 1; 
 
    // Search for a pair 
    while (i < size && j < size) 
    { 
        if (i != j && (arr[j] - arr[i] == n || arr[i] - arr[j] == n) )
        { 
            cout << "Pair Found: (" << arr[i] <<
                        ", " << arr[j] << ")"; 
            return true; 
        } 
        else if (arr[j]-arr[i] < n) 
            j++; 
        else
            i++; 
    } 
 
    cout << "No such pair"; 
    return false; 
} 
 
// Driver program to test above function 
int main() 
{ 
    int arr[] = {1, 8, 30, 40, 100}; 
    int size = sizeof(arr)/sizeof(arr[0]); 
    int n = -60; 
    findPair(arr, size, n); 
    return 0; 
} 
 
// This is code is contributed by rathbhupendra

C

// C program to find a pair with the given difference
#include <stdio.h>
 
// The function assumes that the array is sorted 
int findPair(int arr[], int size, int n)
{
    // Initialize positions of two elements
    int i = 0;  
    int j = 1;
 
    // Search for a pair
    while (i<size && j<size)
    {
        if (i != j && (arr[j] - arr[i] == n || arr[i] - arr[j] == n))
        {
            printf("Pair Found: (%d, %d)", arr[i], arr[j]);
            return 1;
        }
        else if (arr[j]-arr[i] < n)
            j++;
        else
            i++;
    }
 
    printf("No such pair");
    return 0;
}
 
// Driver program to test above function
int main()
{
    int arr[] = {1, 8, 30, 40, 100};
    int size = sizeof(arr)/sizeof(arr[0]);
    int n = -60;
    findPair(arr, size, n);
    return 0;
}

Java

// Java program to find a pair with the given difference
import java.io.*;
 
class PairDifference
{
    // The function assumes that the array is sorted
    static boolean findPair(int arr[],int n)
    {
        int size = arr.length;
 
        // Initialize positions of two elements
        int i = 0, j = 1;
 
        // Search for a pair
        while (i < size && j < size)
        {
            if (i != j && (arr[j] - arr[i] == n || arr[i] - arr[j] == n))
            {
                System.out.print("Pair Found: "+
                                 "( "+arr[i]+", "+ arr[j]+" )");
                return true;
            }
            else if (arr[j] - arr[i] < n)
                j++;
            else
                i++;
        }
 
        System.out.print("No such pair");
        return false;
    }
 
    // Driver program to test above function
    public static void main (String[] args)
    {
        int arr[] = {1, 8, 30, 40, 100};
        int n = -60;
        findPair(arr,n);
    }
}
/*This code is contributed by Devesh Agrawal*/

Python

# Python program to find a pair with the given difference
 
# The function assumes that the array is sorted
def findPair(arr,n):
 
    size = len(arr)
 
    # Initialize positions of two elements
    i,j = 0,1
 
    # Search for a pair
    while i < size and j < size:
 
        if i != j and arr[j]-arr[i] == n:
            print "Pair found (",arr[i],",",arr[j],")"
            return True
 
        elif arr[j] - arr[i] < n:
            j+=1
        else:
            i+=1
    print "No pair found"
    return False
 
# Driver function to test above function
arr = [1, 8, 30, 40, 100]
n = 60
findPair(arr, n)
 
# This code is contributed by Devesh Agrawal

C#

// C# program to find a pair with the given difference
using System;
 
class GFG {
     
    // The function assumes that the array is sorted
    static bool findPair(int []arr, int n)
    {
        int size = arr.Length;
 
        // Initialize positions of two elements
        int i = 0, j = 1;
 
        // Search for a pair
        while (i < size && j < size)
        {
            if (i != j && arr[j] - arr[i] == n)
            {
                Console.Write("Pair Found: "
                + "( " + arr[i] + ", " + arr[j] +" )");
                 
                return true;
            }
            else if (arr[j] - arr[i] < n)
                j++;
            else
                i++;
        }
 
        Console.Write("No such pair");
         
        return false;
    }
 
    // Driver program to test above function
    public static void Main ()
    {
        int []arr = {1, 8, 30, 40, 100};
        int n = 60;
         
        findPair(arr, n);
    }
}
 
// This code is contributed by Sam007.

Javascript

<script>
 
       // JavaScript program for the above approach
 
       // The function assumes that the array is sorted 
       function findPair(arr, size, n) {
           // Initialize positions of two elements 
           let i = 0;
           let j = 1;
 
           // Search for a pair 
           while (i < size && j < size) {
               if (i != j && arr[j] - arr[i] == n) {
                   document.write("Pair Found: (" + arr[i] + ", " +
                   arr[j] + ")");
                   return true;
               }
               else if (arr[j] - arr[i] < n)
                   j++;
               else
                   i++;
           }
 
           document.write("No such pair");
           return false;
       }
 
       // Driver program to test above function 
 
       let arr = [1, 8, 30, 40, 100];
       let size = arr.length;
       let n = 60;
       findPair(arr, size, n);
 
 
   // This code is contributed by Potta Lokesh
  
   </script>

PHP

<?php 
// PHP program to find a pair with
// the given difference
 
// The function assumes that the 
// array is sorted 
function findPair(&$arr, $size, $n)
{
    // Initialize positions of 
    // two elements
    $i = 0; 
    $j = 1;
 
    // Search for a pair
    while ($i < $size && $j < $size)
    {
        if ($i != $j && $arr[$j] - 
                        $arr[$i] == $n)
        {
            echo "Pair Found: " . "(" . 
                  $arr[$i] . ", " . $arr[$j] . ")";
            return true;
        }
        else if ($arr[$j] - $arr[$i] < $n)
            $j++;
        else
            $i++;
    }
 
    echo "No such pair";
    return false;
}
 
// Driver Code
$arr = array(1, 8, 30, 40, 100);
$size = sizeof($arr);
$n = 60;
findPair($arr, $size, $n);
 
// This code is contributed 
// by ChitraNayal
?>

Output

Pair Found: (100, 40)

Time Complexity: O(n*log(n)) [Sorting is still required as first step], Where n is number of element in given array
Auxiliary Space: O(1)

The above code can be simplified and can be made more understandable by reducing bunch of If-Else checks . Thanks to Nakshatra Chhillar for suggesting this simplification. We will understand simplifications through following code:

C++

// C++ program to find a pair with the given difference
#include <bits/stdc++.h>
using namespace std;
bool findPair(int arr[], int size, int n)
{
    // Step-1 Sort the array
    sort(arr, arr + size);
 
    // Initialize positions of two elements
    int l = 0;
    int r = 1;
 
    // take absolute value of difference
    // this does not affect the pair as A-B=diff is same as
    // B-A= -diff
    n = abs(n);
 
    // Search for a pair
 
    // These loop running conditions are sufficient
    while (l <= r and r < size) {
        int diff = arr[r] - arr[l];
        if (diff == n
            and l != r) // we need distinct elements in pair
                        // so l!=r
        {
            cout << "Pair Found: (" << arr[l] << ", "
                 << arr[r] << ")";
            return true;
        }
        else if (diff > n) // try to reduce the diff
            l++;
        else // Note if l==r then r will be advanced thus no
             // pair will be missed
            r++;
    }
    cout << "No such pair";
    return false;
}
 
// Driver program to test above function
int main()
{
    int arr[] = { 1, 8, 30, 40, 100 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int n = -60;
    findPair(arr, size, n);
    cout << endl;
    n = 20;
    findPair(arr, size, n);
    return 0;
}
 
// This code is contributed by Nakshatra Chhillar

Java

// Java program to find a pair with the given difference
import java.io.*;
import java.util.Arrays;
  
class GFG {
static boolean findPair(int arr[], int size, int n)
{
    // Step-1 Sort the array
    Arrays.sort(arr);
 
    // Initialize positions of two elements
    int l = 0;
    int r = 1;
 
    // take absolute value of difference
    // this does not affect the pair as A-B=diff is same as
    // B-A= -diff
    n = Math.abs(n);
 
    // Search for a pair
 
    // These loop running conditions are sufficient
    while (l <= r && r < size) {
        int diff = arr[r] - arr[l];
        if (diff == n
            && l != r) // we need distinct elements in pair
                        // so l!=r
        {
            System.out.print("Pair Found: (" + arr[l] + ", "
                + arr[r] + ")");
            return true;
        }
        else if (diff > n) // try to reduce the diff
            l++;
        else // Note if l==r then r will be advanced thus no
            // pair will be missed
            r++;
    }
    System.out.print("No such pair");
    return false;
}
 
// Driver program to test above function
public static void main (String[] args) 
{
    int arr[] = { 1, 8, 30, 40, 100 };
    int size = arr.length;
    int n = -60;
    findPair(arr, size, n);
    System.out.println();
    n = 20;
    findPair(arr, size, n);
}
}
 
// This code is contributed by Pushpesh Raj

Python3

# Python program to find a pair with the given difference
def findPair( arr, size, n):
    # Step-1 Sort the array
    arr.sort();
     
    # Initialize positions of two elements
    l = 0;
    r = 1;
 
    # take absolute value of difference
    # this does not affect the pair as A-B=diff is same as
    # B-A= -diff
    n = abs(n);
 
    # Search for a pair
 
    # These loop running conditions are sufficient
    while (l <= r and r < size) :
        diff = arr[r] - arr[l];
        if (diff == n and l != r): 
        # we need distinct elements in pair
        # so l!=r
            print("Pair Found: (" , arr[l] , ", "
                 , arr[r] , ")");
            return True;
 
        elif (diff > n):# try to reduce the diff
            l += 1;
        else :# Note if l==r then r will be advanced thus no
             # pair will be missed
            r+=1;
 
    print("No such pair");
    return False;
 
# Driver program to test above function
arr = [ 1, 8, 30, 40, 100 ];
size = len(arr);
n = -60;
findPair(arr, size, n);
n = 20;
findPair(arr, size, n);
 
# This code is contributed by agrawalpoojaa976.

C#

// C# code implementation
using System;
using System.Collections;
public class GFG
{
 
  static bool findPair(int[] arr, int size, int n)
  {
 
    // Step-1 Sort the array
    Array.Sort(arr);
 
    // Initialize positions of two elements
    int l = 0;
    int r = 1;
 
    // take absolute value of difference
    // this does not affect the pair as A-B=diff is same
    // as B-A= -diff
    n = Math.Abs(n);
 
    // Search for a pair
 
    // These loop running conditions are sufficient
    while (l <= r && r < size) {
      int diff = arr[r] - arr[l];
      if (diff == n
          && l != r) // we need distinct elements in
        // pair so l!=r
      {
        Console.Write("Pair Found: (" + arr[l]
                      + ", " + arr[r] + ")");
        return true;
      }
      else if (diff > n) // try to reduce the diff
        l++;
      else // Note if l==r then r will be advanced
        // thus no
        // pair will be missed
        r++;
    }
    Console.Write("No such pair");
    return false;
  }
 
  static public void Main()
  {
 
    // Code
    int[] arr = { 1, 8, 30, 40, 100 };
    int size = arr.Length;
    int n = -60;
    findPair(arr, size, n);
    Console.WriteLine();
    n = 20;
    findPair(arr, size, n);
  }
}
 
// This code is contributed by lokesh.

Javascript

// JavaScript program to find a pair with the given difference
 
const findPair = (arr, size, n) => {
    // Step-1 Sort the array
    arr.sort((a, b) => a - b);
 
    // Initialize positions of two elements
    let l = 0;
    let r = 1;
 
    // take absolute value of difference
    // this does not affect the pair as A-B=diff is same as
    // B-A= -diff
    n = Math.abs(n);
 
    // Search for a pair
 
    // These loop running conditions are sufficient
    while (l <= r && r < size) {
        let diff = arr[r] - arr[l];
        if (diff === n
            && l !== r) // we need distinct elements in pair
                        // so l!==r
        {
            console.log("Pair Found: (" + arr[l] + ", "
                + arr[r] + ")");
            return true;
        }
        else if (diff > n) // try to reduce the diff
            l++;
        else // Note if l==r then r will be advanced thus no
             // pair will be missed
            r++;
    }
    console.log("No such pair");
    return false;
}
 
// Driver program to test above function
const main = () => {
    let arr = [1, 8, 30, 40, 100];
    let size = arr.length;
    let n = -60;
    findPair(arr, size, n);
    console.log();
    n = 20;
    findPair(arr, size, n);
}
 
main();

Output

Pair Found: (40, 100)
No such pair

Time Complexity: O(n*log(n)) [Sorting is still required as first step], Where n is number of element in given array
Auxiliary Space: O(1)

Method 4 :Hashing can also be used to solve this problem. Create an empty hash table HT. Traverse the array, use array elements as hash keys and enter them in HT. Traverse the array again look for value n + arr[i] in HT.

C++

// C++ program to find a pair with the given difference
#include <bits/stdc++.h>
using namespace std;
 
// The function assumes that the array is sorted
bool findPair(int arr[], int size, int n)
{
    unordered_map<int, int> mpp;
    for (int i = 0; i < size; i++) {
        mpp[arr[i]]++;
 
        // Check if any element whose frequency
        // is greater than 1 exist or not for n == 0
        if (n == 0 && mpp[arr[i]] > 1)
            return true;
    }
 
    // Check if difference is zero and
    // we are unable to find any duplicate or
    // element whose frequency is greater than 1
    // then no such pair found.
    if (n == 0)
        return false;
 
    for (int i = 0; i < size; i++) {
        if (mpp.find(n + arr[i]) != mpp.end()) {
            cout << "Pair Found: (" << arr[i] << ", "
                 << n + arr[i] << ")";
            return true;
        }
    }
 
    cout << "No Pair found";
    return false;
}
 
// Driver program to test above function
int main()
{
    int arr[] = { 1, 8, 30, 40, 100 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int n = -60;
    findPair(arr, size, n);
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG
{
 
  // The function assumes that the array is sorted
  static boolean findPair(int[] arr, int size, int n)
  {
    HashMap<Integer,
            Integer> mpp = new HashMap<Integer,
                                      Integer>();
 
     // Traverse the array
    for(int i = 0; i < size; i++)
    {
          
        // Update frequency
        // of arr[i]
        mpp.put(arr[i],
               mpp.getOrDefault(arr[i], 0) + 1);
       
        // Check if any element whose frequency
        // is greater than 1 exist or not for n == 0
        if (n == 0 && mpp.get(arr[i]) > 1)
            return true;
    }
  
     // Check if difference is zero and
    // we are unable to find any duplicate or
    // element whose frequency is greater than 1
    // then no such pair found.
    if (n == 0)
        return false;
 
    for (int i = 0; i < size; i++) {
      if (mpp.containsKey(n + arr[i])) {
        System.out.print("Pair Found: (" + arr[i] + ", " +
                      + (n + arr[i]) + ")");
        return true;
      }
    }
    System.out.print("No Pair found");
    return false;
  }
 
 
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 1, 8, 30, 40, 100 };
    int size = arr.length;
    int n = -60;
    findPair(arr, size, n);
}
}
 
// This code is contributed by code_hunt.

Python3

# Python program to find a pair with the given difference
 
# The function assumes that the array is sorted
def findPair(arr, size, n):
 
    mpp = {}
 
    for i in range(size):
        if arr[i] in mpp.keys():
             mpp[arr[i]] += 1
             if(n == 0 and mpp[arr[i]] > 1): 
                return true;
        else:
             mpp[arr[i]] = 1
     
    if(n == 0):
      return false;
 
    for i in range(size):
         if n + arr[i] in mpp.keys():
            print("Pair Found: (" + str(arr[i]) + ", " + str(n + arr[i]) + ")")
            return True
     
    print("No Pair found")
    return False
 
# Driver program to test above function
arr = [ 1, 8, 30, 40, 100 ]
size = len(arr)
n = -60
findPair(arr, size, n)
 
# This code is contributed by shinjanpatra

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
// The function assumes that the array is sorted
static bool findPair(int[] arr, int size, int n)
{
    Dictionary<int, int> mpp = new Dictionary<int, int>();
 
    // Traverse the array
    for(int i = 0; i < size; i++)
    {
         
        // Update frequency
        // of arr[i]
        mpp[arr[i]]=mpp.GetValueOrDefault(arr[i], 0) + 1;
     
        // Check if any element whose frequency
        // is greater than 1 exist or not for n == 0
        if (n == 0 && mpp[arr[i]] > 1)
            return true;
    }
 
    // Check if difference is zero and
    // we are unable to find any duplicate or
    // element whose frequency is greater than 1
    // then no such pair found.
    if (n == 0)
        return false;
 
    for (int i = 0; i < size; i++) {
    if (mpp.ContainsKey(n + arr[i])) {
        Console.WriteLine("Pair Found: (" + arr[i] + ", " +
                    + (n + arr[i]) + ")");
        return true;
    }
    }
    Console.WriteLine("No Pair found");
    return false;
}
 
// Driver Code
public static void Main(string []args) 
{
    int[] arr = { 1, 8, 30, 40, 100 };
    int size = arr.Length;
    int n = -60;
    findPair(arr, size, n);
}
}
 
// This code is contributed by Aman Kumar

Javascript

<script>
// Javascript program for the above approach
 
// The function assumes that the array is sorted
function findPair(arr, size, n) {
  let mpp = new Map();
 
  // Traverse the array
  for (let i = 0; i < size; i++) {
 
    // Update frequency
    // of arr[i]
    if (mpp.has(arr[i]))
      mpp.set(arr[i], mpp.get(arr[i]) + 1);
    else
      mpp.set(arr[i], 1)
 
    // Check if any element whose frequency
    // is greater than 1 exist or not for n == 0
    if (n == 0 && mpp.get(arr[i]) > 1)
      return true;
  }
 
  // Check if difference is zero and
  // we are unable to find any duplicate or
  // element whose frequency is greater than 1
  // then no such pair found.
  if (n == 0)
    return false;
 
  for (let i = 0; i < size; i++) {
    if (mpp.has(n + arr[i])) {
      document.write("Pair Found: (" + arr[i] + ", " +
        + (n + arr[i]) + ")");
      return true;
    }
  }
  document.write("No Pair found");
  return false;
}
 
// Driver Code
let arr = [1, 8, 30, 40, 100];
let size = arr.length;
let n = -60;
findPair(arr, size, n);
 
// This code is contributed by Saurabh Jaiswal
</script>

Output

Pair Found: (100, 40)

Time Complexity: O(n), Where n is number of element in given array
Auxiliary Space: O(n)

Please write comments if you find any of the above codes/algorithms incorrect, or find other ways to solve the same problem.

GeeksforGeeks

Improve

Previous Article

Sum of two elements whose sum is closest to zero

Kth smallest element in a row-wise and column-wise sorted 2D array

Similar Reads

Pair with given product | Set 1 (Find if any pair exists)

Given an array of distinct elements and a number x, find if there is a pair with a product equal to x. Examples : Input : arr[] = {10, 20, 9, 40}; int x = 400;Output : YesInput : arr[] = {10, 20, 9, 40}; int x = 190;Output : NoInput : arr[] = {-10, 20, 9, -40}; int x = 400;Output : YesInput : arr[] = {-10, 20, 9, 40}; int x = -400;Output : YesInput

Queries to check if any pair exists in an array having values at most equal to the given pair

Given a vector of pairs arr[] and Q queries in the form of pairs in an array Queries[], the task for each query is to check if there exists any pair with both the values smaller than those in the pair of the current query. If found to be true, then print "Yes". Otherwise, print "No". Examples: Input: arr[][] = {{3, 5}, {2, 7}, {2, 3}, {4, 9}}, Quer

Kth smallest pair and number of pairs less than a given pair (x, y)

Given N pairs, the task is to find the Kth smallest pair and the number of pairs less than the given pair (x, y). Examples: Input: pairs[][] = {{23, 20}, {23, 10}, {23, 30}, {12, 35}, {12, 22}}, K = 3, (x, y) = (23, 20) Output: {23, 10} 3 Input: pairs[][] = {{23, 20}, {23, 10}, {23, 30}, {12, 35}, {12, 22}}, K = 2, (x, y) = (12, 35) Output: {12, 35

Pair formation such that maximum pair sum is minimized

Given an array of size 2 * N integers. Divide the array into N pairs, such that the maximum pair sum is minimized. In other words, the optimal division of array into N pairs should result into a maximum pair sum which is minimum of other maximum pair sum of all possibilities. Examples: Input : N = 2 , arr[] = { 5, 8, 3, 9 } Output : (3, 9) (5, 8) E

Probability of a random pair being the maximum weighted pair

Given two arrays A and B, a random pair is picked having an element from array A and another from array B. Output the probability of the pair being maximum weighted. Examples: Input : A[] = 1 2 3 B[] = 1 3 3 Output : 0.222 Explanation : Possible pairs are : {1, 1}, {1, 3}, {1, 3}, {2, 1}, {2, 3}, {2, 3}, {3, 1}, {3, 3}, {3, 3} i.e. 9. The pair with

Store duplicate keys-values pair and sort the key-value pair by key

Given N key-value pairs that contain duplicate keys and values, the task is to store these pairs and sort the pairs by key. Examples: Input : N : 10 Keys : 5 1 4 6 8 0 6 6 5 5 values: 0 1 2 3 4 5 6 7 8 9 Output : Keys : 0 1 4 5 5 5 6 6 6 8 values: 5 1 2 0 8 9 3 6 7 4 Explanation: We have given 10 key, value pairs which contain duplicate keys and va

Count of quadruples with product of a pair equal to the product of the remaining pair

Given an array arr[] of size N, the task is to count the number of unique quadruples (a, b, c, d) from the array such that the product of any pair of elements of the quadruple is equal to the product of the remaining pair of elements. Examples: Input: arr[] = {2, 3, 4, 6}Output: 8Explanation:There are 8 quadruples in the array, i.e. (2, 6, 3, 4), (

Pair the integers of Array so that each pair sum is consecutive and distinct

Given an array arr[]of size N. We have to pair the integers such that each integer should be in exactly one pair and each sum of pairs is consecutive and distinct. Formally, sum(arri + arrj) + 1 = sum(arri1 + arrj1). Print the pairs of integers satisfying all the conditions. If it is not possible to find the pairs return -1. Examples: Input: N = 6,

Reduce Binary Array by replacing both 0s or both 1s pair with 0 and 10 or 01 pair with 1

Given a binary array arr[] of size N, the task is to find the last number remaining in the array after performing a set of operations. In each operation, select any two numbers and perform the following: If both numbers are the same, remove them from the array and insert a 0.If both numbers are different, remove both of them and insert a 1.Example:

Number of indices pair such that element pair sum from first Array is greater than second Array

Given two integer arrays A[] and B[] of equal sizes, the task is to find the number of pairs of indices {i, j} in the arrays such that A[i] + A[j] > B[i] + B[j] and i < j.Examples: Input: A[] = {4, 8, 2, 6, 2}, B[] = {4, 5, 4, 1, 3} Output: 7 Explanation: There are a total of 7 pairs of indices {i, j} in the array following the condition. The

Article Tags :

Practice Tags :