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(N2). 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)