Skip to main content

Count number of pairs (i, j) from an array such that arr[i] * j = arr[j] * i

Given an array arr[] of size N, the task is to count the number of pairs (i, j) possible from the array such that arr[j] * i = arr[i] * j, where 1 ≤ i < j ≤ N.

Examples:

Input: arr[] = 1, 3, 5, 6, 5
Output: 2
Explanation: 
Pair (1, 5) satisfies the condition, since arr[1] * 5 = arr[5] * 1.
Pair (2, 4) satisfies the condition, since arr[2] * 4 = arr[4] * 2. 
Therefore, total number of pairs satisfying the given condition is 2.

Input: arr[] = 2, 1, 3
Output: 0

 

Naive Approach: The simplest approach to solve the problem is to generate all possible pairs from the array and check for each pair, whether the given condition satisfies or not. Increase count for the pairs for which the condition is satisfied. Finally, print the count of all such pairs. 

Below is the implementation of the above idea:

C++




// C++ program for the above approach
 
#include
using namespace std;
 
// Function to count pairs from an
// array satisfying given conditions
void countPairs(int arr[], int N)
    // Stores the total
    // count of pairs
    int count = 0;
 
    for (int i = 1; i <= N; i++)
        for (int j = i + 1; j <= N; j++)
 
            // Note: Indices are 1 based according to
            // question
            if ((arr[j - 1] * i) == (arr[i - 1] * j))
                count++;
            
        
    
 
    cout << count;
 
// Driver Code
int main()
    // Given array
    int arr[] = 1, 3, 5, 6, 5 ;
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call to count pairs
    // satisfying given conditions
    countPairs(arr, N);
 
    return 0;
 















Java

















 






 




 



























// Java program for the above approach


import java.util.*;


 


class GFG


 


    // Function to count pairs from an


    // array satisfying given conditions


    static void countPairs(int[] arr, int N)


    


        // Stores the total


        // count of pairs


        int count = 0;


     


        for (int i = 1; i <= N; i++) 


            for (int j = i + 1; j <= N; j++) 


     


                // Note: Indices are 1 based according to


                // question


                if ((arr[j - 1] * i) == (arr[i - 1] * j)) 


                    count++;


                


            


        


     


        System.out.print(count);


    


     


    // Driver Code


    public static void main(String args[])


    


        // Given array


        int[] arr =  1, 3, 5, 6, 5 ;


     


        // Size of the array


        int N = arr.length;


     


        // Function call to count pairs


        // satisfying given conditions


        countPairs(arr, N);


    








































Python3

















 






 




 



























# Python code for the above approach


 


# Function to count pairs from an


# array satisfying given conditions


def countPairs(arr, N):


    # Stores the total


    # count of pairs


    count = 0


 


    for i in range(1, N+1):


        for j in range(i+1, N+1):


            # Note: Indices are 1 based according to


            # question


            if (arr[j-1] * i) == (arr[i-1] * j):


                count += 1


    print(count)


     


# Given array


arr = [1, 3, 5, 6, 5]


 


# Size of the array


N = len(arr)


 


# Function call to count pairs


# satisfying given conditions


countPairs(arr, N)






































C#

















 






 




 



























// C# code to implement the approach


 


using System;


using System.Collections.Generic;


 


public class Gfg 


    


    // Function to count pairs from an


    // array satisfying given conditions


    static void countPairs(int []arr, int N)


    


        // Stores the total


        // count of pairs


        int count = 0;


     


        for (int i = 1; i <= N; i++) 


            for (int j = i + 1; j <= N; j++) 


     


                // Note: Indices are 1 based according to


                // question


                if ((arr[j - 1] * i) == (arr[i - 1] * j)) 


                    count++;


                


            


        


     


        Console.WriteLine(count);


    


     


    // Driver Code


    public static void Main(string[] args)


    


        // Given array


        int[] arr =  1, 3, 5, 6, 5 ;


     


        // Size of the array


        int N = arr.Length;


     


        // Function call to count pairs


        // satisfying given conditions


        countPairs(arr, N);


     


    








































Javascript

















 






 




 



























// Javascript program for the above approach


 


// Function to count pairs from an


// array satisfying given conditions


function countPairs(arr, N)




    // Stores the total


    // count of pairs


    let count = 0;


 


    for (let i = 1; i <= N; i++) 


        for (let j = i + 1; j <= N; j++) 


 


            // Note: Indices are 1 based according to


            // question


            if ((arr[j - 1] * i) == (arr[i - 1] * j)) 


                count++;


            


        


    


 


    document.write(count);




 


// Driver Code


    // Given array


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


 


    // Size of the array


    let N = arr.length;


     


    // Function call to count pairs


    // satisfying given conditions


    countPairs(arr, N);








































Output

2




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


Efficient Approach: To optimize the above approach, the idea is based on the rearrangement of the given equation arr[i] * j = arr[j] * i to arr[i] / i = arr[j] / j. 
Follow the steps below to solve the problem: 


    

  • Initialize a variable, say count, to store the total count of pairs satisfying the given conditions.
    • 

  • Initialize an Unordered Map, say mp, to count the frequency of values arr[i] / i.
    • 

  • Traverse the array arr[] and update the frequencies of arr[i]/i in the Map.
    • 

  • Print the count as the answer.
    • 



Below is the implementation of the above approach:




C++

















 






 




 



























// C++ program for the above approach


 


#include 


using namespace std;


 


// Function to count pairs from an


// array satisfying given conditions


void countPairs(int arr[], int N)




    // Stores the total


    // count of pairs


    int count = 0;


 


    // Stores count of a[i] / i


    unordered_map<double, int> mp;


 


    // Traverse the array


    for (int i = 0; i < N; i++) 


        double val = 1.0 * arr[i];


        double idx = 1.0 * (i + 1);


 


        // Updating count


        count += mp[val / idx];


 


        // Update frequency


        // in the Map


        mp[val / idx]++;


    


 


    // Print count of pairs


    cout << count;




 


// Driver Code


int main()




    // Given array


    int arr[] =  1, 3, 5, 6, 5 ;


 


    // Size of the array


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


 


    // Function call to count pairs


    // satisfying given conditions


    countPairs(arr, N);


 


    return 0;








































Java

















 






 




 



























// Java program for the above approach


import java.util.*;


 


class GFG


   


// Function to count pairs from an


// array satisfying given conditions


static void countPairs(int []arr, int N)




     


    // Stores the total


    // count of pairs


    int count = 0;


 


    // Stores count of a[i]/i


    Map  mp 


            = new HashMap(); 


 


    // Traverse the array


    for(int i = 0; i < N; i++) 


    


        Double val = 1.0 * arr[i];


        Double idx = 1.0 * (i + 1);


 


        // Updating count


        if (mp.containsKey(val / idx))


            count += mp.get(val/idx);


 


        // Update frequency


        // in the Map


        if (mp.containsKey(val / idx))


            mp.put(val / idx, mp.getOrDefault(val / idx, 0) + 1);


        else


            mp.put(val/idx, 1);


    


 


    // Print count of pairs


    System.out.print(count);




 


// Driver Code


public static void main(String args[])




     


    // Given array


    int []arr =  1, 3, 5, 6, 5 ;


 


    // Size of the array


    int N = arr.length;


 


    // Function call to count pairs


    // satisfying given conditions


    countPairs(arr, N);






 


// This code is contributed by ipg2016107.






































Python3

















 






 




 



























# Python3 program for the above approach


from collections import defaultdict


 


# Function to count pairs from an


# array satisfying given conditions


def countPairs(arr, N):


 


    # Stores the total


    # count of pairs


    count = 0


 


    # Stores count of a[i] / i


    mp = defaultdict(int)


 


    # Traverse the array


    for i in range(N):


        val = 1.0 * arr[i]


        idx = 1.0 * (i + 1)


 


        # Updating count


        count += mp[val / idx]


 


        # Update frequency


        # in the Map


        mp[val / idx] += 1


 


    # Print count of pairs


    print(count)


 


# Driver Code


if __name__ == "__main__":


 


    # Given array


    arr = [1, 3, 5, 6, 5]


 


    # Size of the array


    N = len(arr)


 


    # Function call to count pairs


    # satisfying given conditions


    countPairs(arr, N)


 


# This code is contributed by ukasp






































C#

















 






 




 



























// C# program for the above approach


using System;


using System.Collections.Generic;


 


class GFG


   


// Function to count pairs from an


// array satisfying given conditions


static void countPairs(int []arr, int N)




     


    // Stores the total


    // count of pairs


    int count = 0;


 


    // Stores count of a[i]/i


    Dictionary<double,


               int> mp = new Dictionary<double,


                                        int>();


 


    // Traverse the array


    for(int i = 0; i < N; i++) 


    


        double val = 1.0 * arr[i];


        double idx = 1.0 * (i + 1);


 


        // Updating count


        if (mp.ContainsKey(val / idx))


            count += mp[val/idx];


 


        // Update frequency


        // in the Map


        if (mp.ContainsKey(val / idx))


            mp[val / idx]++;


        else


            mp[val/idx] = 1;


    


 


    // Print count of pairs


    Console.WriteLine(count);




 


// Driver Code


public static void Main()




     


    // Given array


    int []arr =  1, 3, 5, 6, 5 ;


 


    // Size of the array


    int N = arr.Length;


 


    // Function call to count pairs


    // satisfying given conditions


    countPairs(arr, N);






 


// This code is contributed by SURENDRA_GANGWAR






































Javascript

















 






 




 



































































Output: 

2


 




Time Complexity: O(N)
Auxiliary Space: O(N)








                                            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!







 

https://neveropen.tech/count-number-of-pairs-i-j-from-an-array-such-that-arr-i-j-arr-j-i/?feed_id=93&_unique_id=683cf9518a923












Labels:





























Comments











Post a Comment



















Popular posts from this blog





















Bare Metal Billing Client Portal Guide




























      Contents   Order a Bare Metal Server  My Custom / Contract Pricing   View Contract Details   Location Management      Order History & Status   View Order Details         Introduction  The phoenixNAP Client Portal allows you to purchase bare metal servers  and other phoenixNAP products and services. Using the intuitive interface and its essential tools, you can also easily manage your infrastructure.  This quick guide will show you how to use the new form  to order a bare metal server and how to navigate through new bare metal features  within the phoenixNAP Client Portal.     Order a Bare Metal Server  An order form is an accordion-based process for purchasing phoenixNAP products. Our order form allows you to view the pricing and order multiple products from the same category at the same time.     Note:  The prices on the form are per month . A contract is not required. However, if you want a contracted price, you may be eligible for a discount  depending on the quantity and ...




















Post a Comment









Read more






























Add an element in Array  to make the bitwise XOR as K




























   Given an array arr[]  containing N positive integers, the task is to add an integer such that the bitwise Xor of the new array becomes K.  Examples:    Input: arr[] = 1, 4, 5, 6, K = 4 Output: 2 Explanation: Bit-wise XOR of the array is 6.  And bit-wise XOR of 6 and 2 is 4.  Input: arr[] = 2, 7, 9, 1, K = 5 Output:  8        Approach: The solution to the problem is based on the following idea of bitwise Xor:   If for two numbers X  and Y , the bitwise Xor of X and Y is Z  then the bitwise Xor of X and Z is Y.   Follow the steps to solve the problem:   Let the bitwise XOR of the array elements be X .   Say the required value to be added is Y  such that X Xor Y = K .  From the above observation, it is clear that the value to be added (Y) is the same as X Xor K .   Below is the implementation of the above approach:   C++                                 // C++ code to implement the above approach     #include  using  namespace  std;     // Function to find the required value  int  find_...




















Post a Comment









Read more






























Mahotas – Template Matching




























   In this article we will see how we can do template matching in mahotas. Template is basically a part or structure of image. In this tutorial we will use “lena” image, below is the command to load it.    mahotas.demos.load('lena')  Below is the lena image             In order to do this we will use mahotas.template_match method Syntax :  mahotas.template_match(img, template) Argument :  It takes image object and template as argument Return :  It returns image object      Note :  Input image should be filtered or should be loaded as grey In order to filter the image we will take the image object which is numpy.ndarray and filter it with the help of indexing, below is the command to do this    image = image[:, :, 0]  Below is the implementation        Python3                                 # importing required libraries  import  mahotas  import  mahotas.demos  from  pylab import  gray, imshow, show  import  numpy as np  import  matplotlib.pyplot as plt        # loading image  ...




















Post a Comment









Read more