Saturday, July 23, 2022
HomeWordPress DevelopmentDepend of distinct pair sum in given Array

Depend of distinct pair sum in given Array


Given an array arr[] of dimension N, the duty is to search out the entire variety of distinctive pair sums doable from the array parts.

Examples:

Enter: arr[] = {6, 1, 4, 3}
Output: 5
Rationalization: All pair doable are {6, 1}, {6, 4}, {6, 3}, {1, 4}, {1, 3}, {4, 3}. S
ums of those pairs are 7, 10, 9, 5, 4, 7. So distinctive sums 7, 10, 9, 5, 4. So reply is 5.

Enter: arr[] = {8, 7, 6, 5, 4, 3, 2, 1}
Output: 13

 

Strategy: This drawback might be effectively solved through the use of unordered_set. 

Calculate all doable sum of pairs and retailer them in an unordered set. That is completed to retailer the shop parts in a mean time of O(1) with no worth repeating. 

Algorithm:

  • Use nested loops to get all doable sums of parts of the array.
  • Retailer all of the doable sums into an unordered_set.
  • Complete doable distinctive sums can be equal to the scale of unordered_set. So return the scale of the unordered set.

Under is the implementation of the above method:

C++

#embody <bits/stdc++.h>

utilizing namespace std;

  

int rely(int arr[], int n)

{

    unordered_set<int> s;

    

    for (int i = 0; i < n - 1; i++) {

        for (int j = i + 1; j < n; j++) {

            s.insert(arr[i] + arr[j]);

        }

    }

    

    return s.dimension();

}

  

int major()

{

    int arr[] = { 6, 1, 4, 3 };

    int N = sizeof(arr) / sizeof(arr[0]);

  

    

    cout << rely(arr, N);

    return 0;

}

Java

import java.util.*;

  

class GFG {

    

    

    static int rely(int arr[], int n)

    {

        Set<Integer> s = new HashSet<Integer>();

  

        

        for (int i = 0; i < n - 1; i++) {

            for (int j = i + 1; j < n; j++) {

                s.add(arr[i] + arr[j]);

            }

        }

        

        return s.dimension();

    }

  

    

    public static void major(String args[])

    {

        int arr[] = { 6, 1, 4, 3 };

        int N = arr.size;

  

        

        System.out.println(rely(arr, N));

    }

}

Python3

  

def rely(arr, n):

    s = set()

      

    

    for i in vary(n-1):

        for j in vary(i + 1, n):

            s.add(arr[i] + arr[j])

  

    

    return int(len(s))

  

if __name__ == '__main__':

    arr = [6, 1, 4, 3]

    N = len(arr)

      

    

    print(rely(arr, N))

Javascript

<script>

  

  

operate rely(arr, n) {

    let s = new Set();

    

    for (let i = 0; i < n - 1; i++) {

        for (let j = i + 1; j < n; j++) {

            s.add(arr[i] + arr[j]);

        }

    }

    

    return s.dimension;

}

  

let arr = [6, 1, 4, 3];

let N = arr.size;

  

doc.write(rely(arr, N));

  

</script>

Time complexity: O(N2)
Auxiliary House: O(N)

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments