Given an array arr[] of length N with distinct integers from 1 to 2*N, the task is to count the number of pairs of indices (i, j) such that (i < j) and arr[i] * arr[j] = i + j, i.e. calculate the number of pairs such that their product is equal to their sum of indices.
Examples:
Input: N = 5, arr[] = {3, 1, 5, 9, 2}
Output: 3
Explanation: There are three pairs (i, j) such that (i < j) and arr[i] * arr[j] = i + j (1, 2), (1, 5), (2, 3)Input: N = 3, arr[] = {6, 1, 5}
Output: 1
Naive Approach: Iterate over all pairs of indices (i, j) with (i < j) and check for each pair if the above condition is satisfied, then increase the answer by 1 otherwise go to the next pair.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the number of// unique pairsint NumberOfRequiredPairs(int arr[], int N){ // Variable that with stores number // of valid pairs int ans = 0; // Traverse the array for every // possible index i for (int i = 0; i < N; i++) // Traverse the array for every // possible j (i < j) // Please note that the indices // are used as 1 based indexing for (int j = i + 1; j < N; j++) if ((arr[i] * arr[j]) == ((i + 1) + (j + 1))) ans++; // Return the ans return ans;}// Driver Codeint main(){ // Given Input int N = 5; int arr[] = { 3, 1, 5, 9, 2 }; // Function Call cout << NumberOfRequiredPairs(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{// Function to find the number of// unique pairsstatic int NumberOfRequiredPairs(int arr[], int N){ // Variable that with stores number // of valid pairs int ans = 0; // Traverse the array for every // possible index i for (int i = 0; i < N; i++) // Traverse the array for every // possible j (i < j) // Please note that the indices // are used as 1 based indexing for (int j = i + 1; j < N; j++) if ((arr[i] * arr[j]) == ((i + 1) + (j + 1))) ans++; // Return the ans return ans;}// Driver codepublic static void main (String[] args){ // Given Input int N = 5; int arr[] = { 3, 1, 5, 9, 2 }; // Function Call System.out.println(NumberOfRequiredPairs(arr, N));}}// This code is contributed by sanjoy_62. |
Python3
# Python program for the above approach# Function to find the number of# unique pairsdef NumberOfRequiredPairs(arr, N): # Variable that with stores number # of valid pairs ans = 0 # Traverse the array for every # possible index i for i in range(N): # Traverse the array for every # possible j (i < j) # Please note that the indices # are used as 1 based indexing for j in range(i + 1, N): if ((arr[i] * arr[j]) == ((i + 1) + (j + 1))): ans += 1 # Return the ans return ans# Driver Code# Given InputN = 5arr = [3, 1, 5, 9, 2]# Function Callprint(NumberOfRequiredPairs(arr, N))# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing System;class GFG{// Function to find the number of// unique pairsstatic int NumberOfRequiredPairs(int []arr, int N){ // Variable that with stores number // of valid pairs int ans = 0; // Traverse the array for every // possible index i for (int i = 0; i < N; i++) // Traverse the array for every // possible j (i < j) // Please note that the indices // are used as 1 based indexing for (int j = i + 1; j < N; j++) if ((arr[i] * arr[j]) == ((i + 1) + (j + 1))) ans++; // Return the ans return ans;}// Driver codepublic static void Main (){ // Given Input int N = 5; int []arr = { 3, 1, 5, 9, 2 }; // Function Call Console.Write(NumberOfRequiredPairs(arr, N));}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// Javascript program for the above approach// Function to find the number of// unique pairsfunction NumberOfRequiredPairs(arr, N){ // Variable that with stores number // of valid pairs let ans = 0; // Traverse the array for every // possible index i for (let i = 0; i < N; i++) // Traverse the array for every // possible j (i < j) // Please note that the indices // are used as 1 based indexing for (let j = i + 1; j < N; j++) if ((arr[i] * arr[j]) == ((i + 1) + (j + 1))) ans++; // Return the ans return ans;}// Driver Code// Given Inputlet N = 5;let arr = [ 3, 1, 5, 9, 2 ];// Function Calldocument.write(NumberOfRequiredPairs(arr, N));// This code is contributed by Samim Hossain Mondal.</script> |
Output
3
Time Complexity: O(N^2)
Auxiliary Space: O(1)
Efficient Approach : Rewrite the mentioned condition as
arr[j] = (i + j)/arr[i]
Therefore, for each multiple of arr[i], find the respective j and check whether arr[j] is equal to (i + j)/ arr[i]. This approach is efficient because for each i it is required to go through each multiple of i till 2*N. As all numbers in the array are distinct, it can be concluded that the total iterations for calculating j will be like:
N + N/2 + N/3 + N/4 + N/5……
This is a well-known result of the series of expansions of logN. For more information read about this here. Follow the steps below to solve the problem:
- Initialize the variable ans as 0 to store the answer.
- Iterate over the range [0, N] using the variable i and perform the following steps:
- Initialize the variable k as the value of arr[i].
- Iterate in a while loop till k is less than equal to 2*N and perform the following tasks:
- Initialize the variable j as k-i-1.
- If j is greater than equal to 1 and less than equal to N and arr[j – 1] is equal to k / arr[i] and j is greater than i+1, then increase the value of ans by 1.
- After performing the above steps, print the value of ans as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the number of// unique pairsint NumberOfRequiredPairs(int arr[], int N){ // Variable that with stores // number of valid pairs int ans = 0; // Traverse the array for every // possible index i for (int i = 0; i < N; i++) { // Initialize a dummy variable // for arr[i] int k = arr[i]; // We will loop through every // multiple of arr[i]; // Looping through 2*N because // the maximum element // in array can be 2*N // Please not that i and j are // in 1 based indexing while (k <= 2 * N) { // Calculating j int j = k - i - 1; // Now check if this j lies // between the bounds // of the array if (j >= 1 && j <= N) { // Checking the required // condition if ((arr[j - 1] == k / arr[i]) && j > i + 1) { ans++; } } // Increasing k to its next multiple k += arr[i]; } } // Return the ans return ans;}// Driver Codeint main(){ // Given Input int N = 5; int arr[] = { 3, 1, 5, 9, 2 }; // Function Call cout << NumberOfRequiredPairs(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG{// Function to find the number of// unique pairsstatic int NumberOfRequiredPairs(int arr[], int N){ // Variable that with stores // number of valid pairs int ans = 0; // Traverse the array for every // possible index i for (int i = 0; i < N; i++) { // Initialize a dummy variable // for arr[i] int k = arr[i]; // We will loop through every // multiple of arr[i]; // Looping through 2*N because // the maximum element // in array can be 2*N // Please not that i and j are // in 1 based indexing while (k <= 2 * N) { // Calculating j int j = k - i - 1; // Now check if this j lies // between the bounds // of the array if (j >= 1 && j <= N) { // Checking the required // condition if ((arr[j - 1] == k / arr[i]) && j > i + 1) { ans++; } } // Increasing k to its next multiple k += arr[i]; } } // Return the ans return ans;}// Driver codepublic static void main (String args[]){ // Given Input int N = 5; int arr[] = { 3, 1, 5, 9, 2 }; // Function Call System.out.println(NumberOfRequiredPairs(arr, N));}}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python3 program for the above approach# Function to find the number of# unique pairsdef NumberOfRequiredPairs(arr, N) : # Variable that with stores # number of valid pairs ans = 0; # Traverse the array for every # possible index i for i in range(N) : # Initialize a dummy variable # for arr[i] k = arr[i]; # We will loop through every # multiple of arr[i]; # Looping through 2*N because # the maximum element # in array can be 2*N # Please not that i and j are # in 1 based indexing while (k <= 2 * N) : # Calculating j j = k - i - 1; # Now check if this j lies # between the bounds # of the array if (j >= 1 and j <= N) : # Checking the required # condition if ((arr[j - 1] == k // arr[i]) and j > i + 1) : ans += 1; # Increasing k to its next multiple k += arr[i]; # Return the ans return ans;# Driver Codeif __name__ == "__main__" : # Given Input N = 5; arr = [ 3, 1, 5, 9, 2 ]; # Function Call print(NumberOfRequiredPairs(arr, N)); # This code is contributed by AnkThon |
C#
// C# program for the above approachusing System;class GFG{// Function to find the number of// unique pairsstatic int NumberOfRequiredPairs(int []arr, int N){ // Variable that with stores // number of valid pairs int ans = 0; // Traverse the array for every // possible index i for (int i = 0; i < N; i++) { // Initialize a dummy variable // for arr[i] int k = arr[i]; // We will loop through every // multiple of arr[i]; // Looping through 2*N because // the maximum element // in array can be 2*N // Please not that i and j are // in 1 based indexing while (k <= 2 * N) { // Calculating j int j = k - i - 1; // Now check if this j lies // between the bounds // of the array if (j >= 1 && j <= N) { // Checking the required // condition if ((arr[j - 1] == k / arr[i]) && j > i + 1) { ans++; } } // Increasing k to its next multiple k += arr[i]; } } // Return the ans return ans;}// Driver codepublic static void Main (){ // Given Input int N = 5; int []arr = { 3, 1, 5, 9, 2 }; // Function Call Console.Write(NumberOfRequiredPairs(arr, N));}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// Javascript program for the above approach// Function to find the number of// unique pairsfunction NumberOfRequiredPairs(arr, N){ // Variable that with stores // number of valid pairs let ans = 0; // Traverse the array for every // possible index i for (let i = 0; i < N; i++) { // Initialize a dummy variable // for arr[i] let k = arr[i]; // We will loop through every // multiple of arr[i]; // Looping through 2*N because // the maximum element // in array can be 2*N // Please not that i and j are // in 1 based indexing while (k <= 2 * N) { // Calculating j let j = k - i - 1; // Now check if this j lies // between the bounds // of the array if (j >= 1 && j <= N) { // Checking the required // condition if ((arr[j - 1] == k / arr[i]) && j > i + 1) { ans++; } } // Increasing k to its next multiple k += arr[i]; } } // Return the ans return ans;}// Driver Code// Given Inputlet N = 5;let arr = [ 3, 1, 5, 9, 2 ];// Function Calldocument.write(NumberOfRequiredPairs(arr, N));// This code is contributed by Samim Hossain Mondal.</script> |
Output
3
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
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!
