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

Comments

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 ...

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_...

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 ...