Print distinct absolute differences of all possible pairs from a given array

0 0 7 minutes read

Given an array, arr[] of size N, the task is to find the distinct absolute differences of all possible pairs of the given array.

Examples:

Input: arr[] = { 1, 3, 6 }
Output: 2 3 5
Explanation:
abs(arr[0] – arr[1]) = 2
abs(arr[1] – arr[2]) = 3
abs(arr[0] – arr[2]) = 5

Input: arr[] = { 5, 6, 7, 8, 14, 19, 21, 22 }
Output: 1 2 3 5 6 7 8 9 11 12 13 14 15 16 17

Naive Approach: The simplest approach to solve this problem is to generate all possible pairs of the given array and insert the absolute difference of each pair in a Set. Finally, print all the elements of the set.
Time Complexity: O(N² * log(N))
Auxiliary Space: O(N²)

Approach: The above approach can be optimized using Bitset. Follow the steps below to solve the problem:

Initialize a Bitset, say bset, where bset[i] check if i is present in the array or not.
Traverse the array arr[] and store all the array elements in the bset.
Initialize a Bitset, say diff, where diff[i] stores if the absolute difference of there exists any pair in the array whose value equal to i or not.
Find the largest element of the array, say Max
Iterate over the range [0, Max]. In every i^th iteration check if bset[i] is true or not. If found to be true, then insert the absolute difference of i with all other array elements using diff = diff | (bset >> i).
Finally, iterate over the range [0, Max] and check if diff[i] is true or not. If found to be true, then print i.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
#define Max 100005
 
// Function to find all distinct
// absolute difference of all
// possible pairs of the array
void printUniqDif(int n, int a[])
{
 
    // bset[i]: Check if i is present
    // in the array or not
    bitset<Max> bset;
 
    // diff[i]: Check if there exists a
    // pair whose absolute difference is i
    bitset<Max> diff;
 
    // Traverse the array, arr[]
    for (int i = 0; i < n; i++) {
 
        // Add in bitset
        bset.set(a[i]);
    }
 
    // Iterate over the range[0, Max]
    for (int i = 0; i <= Max; i++) {
 
        // If i-th bit is set
        if (bset[i]) {
 
            // Insert the absolute difference
            // of all possible pairs whose
            // first element is arr[i]
            diff = diff | (bset >> i);
        }
    }
 
    // Stores count of set bits
    int X = bset.count();
 
    // If there is at least one
    // duplicate element in arr[]
    if (X != n) {
 
        cout << 0 << " ";
    }
 
    // Printing the distinct absolute
    // differences of all possible pairs
    for (int i = 1; i <= Max; i++) {
 
        // If i-th bit is set
        if (diff[i]) {
            cout << i << " ";
        }
    }
}
 
// Driver Code
int main()
{
 
    // Given array
    int a[] = { 1, 4, 6 };
 
    // Given size
    int n = sizeof(a) / sizeof(a[0]);
 
    // Function Call
    printUniqDif(n, a);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG
{
  static int Max = 100005;
 
  // Function to find all distinct
  // absolute difference of all
  // possible pairs of the array
  static void printUniqDif(int n, int[] a)
  {
    // bset[i] Check if i is present
    // in the array or not
    int[] bset = new int[33];
 
    // diff[i] Check if there exists a
    // pair whose absolute difference is i
    int diff = 0;
 
    // Traverse the array, arr[]
    for (var i = 0; i < n; i++)
      bset[a[i]] = 1;
 
    // Iterate over the range[0, Max]
    int d = 0;
 
    for (var i = 0; i < 33; i++)
      d = d | (bset[i] << i);
 
    for (var i = 0; i < 33; i++)
    {
      // If i-th bit is set
      if (bset[i] == 1)
 
        // Insert the absolute difference
        // of all possible pairs whose
        // first element is arr[i]
        diff |= (d >> i);
    }
 
    // Stores count of set bits
    int X =  0;
    for (int i = 0; i < 33; i++)
        if (bset[i] == 1)
            X++;
 
    String Y =Integer.toBinaryString(diff); 
 
    // If there is at least one
    // duplicate element in arr[]
    if (X != n)
      System.out.print("0 ");
 
    // Printing the distinct absolute
    // differences of all possible pairs
    for (var i = 1; i < Y.length(); i++)
    {
       
      // If i-th bit is set
      if (Y.charAt(i) == '1')
        System.out.print(i + " ");
    }
  }
 
  // Driver Code
  public static void main(String[] args)
  {
     
    // Given array
    int[] a = {1, 4, 6};
 
    // Given size
    int n = a.length;
 
    // Function Call
    printUniqDif(n, a);
  }
}
// This code is contributed by phasing17

Python3

# Python3 program for the above approach
Max = 100005
 
# Function to find all distinct
# absolute difference of all
# possible pairs of the array
def printUniqDif(n, a):
 
    # bset[i]: Check if i is present
    # in the array or not
    bset = [0 for i in range(33)]
 
    # diff[i]: Check if there exists a
    # pair whose absolute difference is i
    diff = 0
 
    # Traverse the array, arr[]
    for i in range(n):
        bset[a[i]] = 1
 
    # Iterate over the range[0, Max]
    d = 0
 
    for i in range(1,33):
        d = d | (bset[i]<<i)
 
    for i in range(33):
 
        # If i-th bit is set
        if (bset[i]):
 
            # Insert the absolute difference
            # of all possible pairs whose
            # first element is arr[i]
            diff = diff | d >> i
            # print(bin(diff))
 
    # Stores count of set bits
    X, Y = bset.count(1), str(bin(diff)[2:])
 
    # If there is at least one
    # duplicate element in arr[]
    if (X != n):
 
        print(0, end=" ")
 
    # Printing the distinct absolute
    # differences of all possible pairs
    for i in range(1, len(Y)):
 
        # If i-th bit is set
        if (Y[i] == '1'):
            print(i, end = " ")
# Driver Code
if __name__ == '__main__':
 
    # Given array
    a = [1, 4, 6]
 
    # Given size
    n = len(a)
 
    # Function Call
    printUniqDif(n, a)
 
    # This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG
{
  static int Max = 100005;
 
  // Function to find all distinct
  // absolute difference of all
  // possible pairs of the array
  static void printUniqDif(int n, int[] a)
  {
    // bset[i] Check if i is present
    // in the array or not
    int[] bset = new int[33];
 
    // diff[i] Check if there exists a
    // pair whose absolute difference is i
    int diff = 0;
 
    // Traverse the array, arr[]
    for (var i = 0; i < n; i++)
      bset[a[i]] = 1;
 
    // Iterate over the range[0, Max]
    int d = 0;
 
    for (var i = 0; i < 33; i++)
      d = d | (bset[i] << i);
 
    for (var i = 0; i < 33; i++)
    {
      // If i-th bit is set
      if (bset[i] == 1)
 
        // Insert the absolute difference
        // of all possible pairs whose
        // first element is arr[i]
        diff |= (d >> i);
    }
 
    // Stores count of set bits
    int X =  bset.Count(f => f == 1);
 
    string Y = Convert.ToString(diff, 2);
 
    // If there is at least one
    // duplicate element in arr[]
    if (X != n)
      Console.Write("0 ");
 
    // Printing the distinct absolute
    // differences of all possible pairs
    for (var i = 1; i < Y.Length; i++)
    {
      // If i-th bit is set
      if (Y[i] == '1')
        Console.Write(i + " ");
    }
  }
 
  // Driver Code
 
  public static void Main(string[] args)
  {
    // Given array
    int[] a = {1, 4, 6};
 
    // Given size
    int n = a.Length;
 
    // Function Call
    printUniqDif(n, a);
  }
}
 
// This code is contributed by phasing17

Javascript

// JS program for the above approach
let Max = 100005
 
// Function to find all distinct
// absolute difference of all
// possible pairs of the array
function printUniqDif(n, a)
{
    // bset[i] Check if i is present
    // in the array or not
    let bset = new Array(33).fill(0) 
 
    // diff[i] Check if there exists a
    // pair whose absolute difference is i
    let diff = 0
 
    // Traverse the array, arr[]
    for (var i = 0; i < n; i++)
        bset[a[i]] = 1
 
    // Iterate over the range[0, Max]
    let d = 0
     
    for (var i = 0; i < 33; i++)
        d = d | (bset[i] << i)
 
    for (var i = 0; i < 33; i++)
    {
        // If i-th bit is set
        if (bset[i] == 1)
 
            // Insert the absolute difference
            // of all possible pairs whose
            // first element is arr[i]
            diff |= (d >> i)
    }
     
    // Stores count of set bits
    let X = bset.filter(x => x == 1).length
     
    let Y = diff.toString(2)
     
 
 
    // If there is at least one
    // duplicate element in arr[]
    if (X != n)
        process.stdout.write("0 ")
 
    // Printing the distinct absolute
    // differences of all possible pairs
    for (var i = 1; i < Y.length; i++)
 
        // If i-th bit is set
        if (Y.charAt(i) == '1')
            process.stdout.write(i + " ")
}
             
// Driver Code
 
// Given array
let a = [1, 4, 6]
 
// Given size
let n = a.length
 
// Function Call
printUniqDif(n, a)
 
 
// This code is contributed by phasing17

Output:

2 3 5

Time Complexity:O(N + Max), where Max is the largest element of the array.
Auxiliary Space: O(Max)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!