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(N2 * log(N))
Auxiliary Space: O(N2)
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 ith 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 arrayvoid 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 Codeint 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 approachimport 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 approachMax = 100005# Function to find all distinct# absolute difference of all# possible pairs of the arraydef 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 Codeif __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 approachusing 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 approachlet Max = 100005// Function to find all distinct// absolute difference of all// possible pairs of the arrayfunction 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 arraylet a = [1, 4, 6]// Given sizelet n = a.length// Function CallprintUniqDif(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
