Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Depend of pairs in Array with product higher than 0

[ad_1]

Given an array arr[] of size N, the duty is to depend the variety of pairs (i, j) such that arr[i] * arr[j] > 0 and 0 ≤ i < j ≤ N. Additionally it is on condition that component of the array will be any optimistic integer together with zero or will be damaging integer.

Examples:

Enter: arr[] = {1, -5, 0, 2, -7} 
Output: 2
Clarification: Right here product of (1, 2) and (-5, -7) is larger than 0.

Enter: arr[] = {0, 1, 5, 9}
Output: 3

 

Naive method: The essential method is to generate all potential pairs of the array and depend these pairs which fulfill the given situation.

Observe the steps talked about beneath to implement the concept:

  • Use a nested loop to generate all pairs.
  • Verify if the product of the pair is larger than 0, then enhance the depend.
  • Return the ultimate depend after producing all pairs.

Observe the steps talked about beneath to implement the method.

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

lengthy countPairs(int arr[], int n)

{

    lengthy depend = 0;

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

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

  

            

            

            if (arr[i] * arr[j] > 0)

                depend++;

        }

    }

  

    

    return depend;

}

  

int important()

{

    int arr[] = { 1, -5, 0, 2, -7 };

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

  

    

    cout << countPairs(arr, N);

    return 0;

}

Java

  

class GFG {

  

    

    

    static lengthy countPairs(int arr[], int n)

    {

        lengthy cnt = 0;

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

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

  

                

                

                if (arr[i] * arr[j] > 0)

                    cnt++;

            }

        }

  

        

        return cnt;

    }

  

    

    public static void important(String[] args)

    {

        int arr[] = { 1, -5, 0, 2, -7 };

        int N = arr.size;

  

        

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

    }

}

Python3

  

def countPairs(arr, n) :

    cnt = 0;

    for i in vary(n - 1) :

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

  

            

            

            if (arr[i] * arr[j] > 0) :

                cnt += 1;

  

    

    return cnt;

  

if __name__ == "__main__" :

    arr = [ 1, -3, 0, 2, -1 ];

    N = len(arr);

  

    

    print(countPairs(arr, N));

Time Complexity: O(N2)
Auxiliary Area: O(1)

Environment friendly Method: The issue will be solved based mostly on the next thought:

Multiplication of two numbers will be higher than zero provided that each the numbers are damaging or each the numbers are optimistic. And if one quantity is zero then it cannot type pair with anybody with a view to get the end result as higher than zero. 

To implement the concept depend the optimistic numbers & damaging numbers. Then get the variety of pairs utilizing the components of combinatorics nC2 that’s (optimistic*(positive-1)/2 + damaging*(damaging*-1)/2 ). Observe the beneath steps to implement the concept:

  • Run a loop from i = 0 to N-1: 
    • Depend the variety of optimistic and damaging numbers within the array (say represented by optimistic and damaging).
  • Now calculate the whole pairs attributable to incidence of optimistic and complete pairs attributable to incidence of damaging utilizing the above commentary.
  • Return the whole variety of occurrences.

Beneath is the implementation for the above implementation:

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

lengthy countPairs(int arr[], int n)

{

    int optimistic = 0;

    int damaging = 0;

  

    

    

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

        if (arr[i] == 0)

            proceed;

        else if (arr[i] > 0)

            optimistic++;

  

        else

            damaging++;

    }

  

    

    lengthy pos = (optimistic * (optimistic - 1)) / 2;

  

    

    lengthy neg = (damaging * (damaging - 1)) / 2;

  

    

    return pos + neg;

}

  

int important()

{

    int arr[] = { 1, -5, 0, 2, -7 };

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

  

    

    cout << countPairs(arr, N);

    return 0;

}

Java

  

class GFG {

  

    

    

    static lengthy countPairs(int arr[], int n)

    {

        int optimistic = 0;

        int damaging = 0;

  

        

        

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

            if (arr[i] == 0)

                proceed;

            else if (arr[i] > 0)

                optimistic++;

  

            else

                damaging++;

        }

  

        

        

        lengthy pos = (optimistic

                    * (optimistic - 1))

                   / 2;

  

        

        

        lengthy neg = (damaging

                    * (damaging - 1))

                   / 2;

  

        

        return pos + neg;

    }

  

    

    public static void important(String[] args)

    {

        int arr[] = { 1, -5, 0, 2, -7 };

        int N = arr.size;

  

        

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

    }

}

Time Complexity: O(N)
Auxiliary Area: O(1)

[ad_2]

Leave a Reply