Table of contents

Introduction

1.1.

Problem Statement

1.2.

Sample Examples

Brute Force Approach

2.1.

Steps of algorithm

2.2.

Implementation in C++

2.2.1.

Complexity Analysis

Optimal Approach

3.1.

Steps of algorithm

3.2.

Implementation in C++

3.2.1.

Complexity Analysis

Frequently asked questions

Key takeaways

Last Updated: Mar 27, 2024

Count of unordered pair of indices such that the ratio of elements at these indices is same as the ratio of indices

Q: Q1. What is time complexity?

Ans. The time complexity can be defined as the time taken by the computer to run an algorithm.

Q: Q2. What is the Sieve of Eratosthenes?

Ans. Sieve of Eratosthenes is an algorithm by which we can calculate the number of prime numbers in a given range and the time complexity is far less than the standard method of calculating the prime numbers in the given range.

Q: Q3. What is a Subsequence?

Ans. A subsequence is a sequence that can be derived from a sequence by deleting some elements of that sequence, but the order remains unchanged.

Author Vibhor Bhatnagar

Introduction

Problem Statement

The problem is to get the count of unordered pair of indices such that the ratio of elements at these indices is same as the ratio of indices we are given an array of length N, we have to find the count of the unordered pairs (i, j) in the array such that ratio of elements of these indices is same as the ratio of indices (arr[i]/arr[j] = i/j). So before we look into the solution to this problem, we should first look at some examples to understand the problem better.

Sample Examples

Example 1:

Input: arr[]= {4, 1, 12, 5}

Output: 1

Explanation:
The pair is:
(1, 3) as arr[3] / arr[1] = 12 / 4 = 3

Example 2:

Input: arr[]= {7, 14, 21, 28, 2}

Output: 4

Explanation:
The pairs are:
(1, 2) as arr[2] / arr[1] = 14/7 = 2
(2, 4) as arr[4] / arr[2] = 28/14 = 2
(1, 3) as arr[3] / arr[1] = 21/7 = 3
(1, 4) as arr[4] / arr[1] = 28/7 = 4

Also see, Euclid GCD Algorithm

Brute Force Approach

This problem to find the count of unordered pair of indices such that the ratio of elements at these indices is same as the ratio of indices can be solved using two nested for loops considering each possible pair (i,j)

Steps of algorithm

We will check for every pair of (i, j), and whichever pair follows the condition, we increase the count of the answer.
After that, we will return the answer.

Implementation in C++

// C++ code to get the count of unordered pair of indices such that the ratio of elements at these indices is same as the ratio of indices
#include <bits/stdc++.h>
using namespace std;

int countPairs(int a[], int n)
{
    // to store the count of valid pairs
    int ans = 0;

    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            // to check if the pair is valid
            if ((a[j] % a[i] == 0) && ((j + 1) % (i + 1)) == 0 && (a[j] / a[i] == (j + 1) / (i + 1)))
            {
                ans++;
            }
        }
    }

    // return the answer
    return ans;
}

// Driver Code
int main()
{
    int arr[] = {5, 10, 4, 1, 6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Function Call
    cout << countPairs(arr, n);

    return 0;
}

Output:

Input:  arr={5, 10, 4, 1, 6, 8}
Output: 2

Complexity Analysis

Time Complexity: O(N*N)

Since we are using two nested loops to solve the above problem, therefore, the time complexity of the approach is O(N*N).

Space Complexity: O(1)

Optimal Approach

The brute force approach of this problem can be optimized by the idea that the maximum value of (i/j) can be N and also that i must be divisible by j.

Steps of algorithm

So will iterate for i in the range [1, N], and we will iterate over the j in the range [1, N] such that j is divisible by i, and we will store the count of all the valid pairs in the answer variable.
This can be done by using the method of Sieve of Eratosthenes.
Now we will return the final answer, which was stored in the variable.

Implementation in C++

// C++ code to find the count of unordered pair of indices such that the ratio of elements at these indices is same as the ratio of indices
#include <bits/stdc++.h>
using namespace std;

int countPairs(int arr[], int n)
{
    // to store the count of valid pairs
    int ans = 0;

    // to iterate over all values of i i.e., [1, N]
    for (int i = 1; i <= n; i++)
    {

        // to iterate over all the possible values
        // of j that are the divisble by i
        for (int j = 2 * i; j <= n; j += i)
        {

            if ((arr[j - 1] % arr[i - 1] == 0) && (arr[j - 1] / arr[i - 1] == j / i))
            {
                ans++;
            }
        }
    }

    // Return answer
    return ans;
}

// Driver Code
int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Function Call
    cout << countPairs(arr, n);

    return 0;
}

Output:

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

Complexity Analysis

Time Complexity: O(N*(logN))

Space Complexity: O(1)

Frequently asked questions

Q1. What is time complexity?

Ans. The time complexity can be defined as the time taken by the computer to run an algorithm.

Q2. What is the Sieve of Eratosthenes?

Ans. Sieve of Eratosthenes is an algorithm by which we can calculate the number of prime numbers in a given range and the time complexity is far less than the standard method of calculating the prime numbers in the given range.

Q3. What is a Subsequence?

Ans. A subsequence is a sequence that can be derived from a sequence by deleting some elements of that sequence, but the order remains unchanged.

Key takeaways

This article discussed the problem of finding the count of unordered pair of indices such that the ratio of elements at these indices is same as the ratio of indices, and we have also discussed its two approaches one is brute force approach, and another is the optimal approach which is solved using the method of Sieve of Eratosthenes.