Count of elements A[i] such that A[i] * K is also present in the Array

Given an integer array arr[] and K, the task is to count the number of elements ‘A[i]’, such that A[i] * K is also present in the array.
Note: If there are duplicates in the array, count them separately.

Examples:

Input : arr = { 2, 4, 5, 7, 10}, K = 2
Output : 2
Explanation :
For element 2, 2*2 = 4 is present in arr.
For element 5, 5*2 = 10 is present in arr.

Input : arr = { 5, 10, 15, 20, 30}, K = 3
Output : 2
Explanation :
For element 5, 5*3 = 15 is present in arr.
For element 10, 10*3 = 30 is present in arr.

Approach-1: Brute Force Solution
For all the elements in the array, return the total count after examining all elements

For current element x, compute x * K, and search all positions before and after the current value for x * K.
If you find x * K, add 1 to the total count.

Time Complexity of Approach 1 is O(N²). Space Complexity of Approach 1 is O(1).

Approach-2: Using Map
Add all elements in the array to the map.
Again, for all elements in the array, say x, check if x * K exists in the map. If it exists, increment the counter.
Return the total count after examining all keys in the map.

Below is the implementation of the above approach:

// C++ program to count elements
// A[i] such that A[i] * K
// is also present in the Array

#include <bits/stdc++.h>
using namespace std;

// Function to find the countElements
int countElements(vector<int>& arr, int K)
{
    int size = arr.size();

    // Initialize result as zero
    int res = 0;

    // Create map
    unordered_map<int, bool> dat;

    // First loop to fill the map
    for (int i = 0; i < size; ++i) {
        dat[arr[i]] = true;
    }

    // Second loop to check the map
    for (int i = 0; i < size; ++i) {
        if (dat[arr[i] * K] == true) {
            res++;
        }
    }
    return res;
}

// Driver program
int main()
{
    // Input Array
    vector<int> arr = {2, 4, 5, 7, 10};
    int K = 2;

    // Call the countElements function
    cout << countElements(arr, K) << endl;

    return 0;
}

Output :

2

Time Complexity : O(n)
Space Complexity : O(n)