Problem Statement:
You are given an array, you need to check if a number and its double exist in that array.
Example
Input arr = {10, 2, 5, 3}
Output: True
N = 5 M = 10. 5*2 = 10. So there exist 2 integers, such that the integer and its double exist.
Solution
In this solution, we will use hash map.
At every index, we check for 2 cases:
Case 1: If we find the double of the element in the map, then we return true. This is for odd numbers
Case 2: We divide the current element by 2 and find if the arr[i]/2 element is present then we return true. This is for even numbers.
else we just insert that element into the array.
Solution in C++
#include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <stack> #include <vector> #include <unordered_map> #include <queue> using namespace std; bool check_if_exist(vector<int>& arr) { unordered_map<int, int> mp; for(int i = 0; i < arr.size(); i++) { if(mp.find(arr[i] * 2) != mp.end()) return true; if(arr[i] % 2 == 0 && mp.find(arr[i]/2) != mp.end()) return true; mp[arr[i]]++; } return false; } int main() { vector<int> arr = {10,2,5,3}; if(check_if_exist(arr)) { cout<<"There are 2 element exist"<<endl; } else { cout<<"There are no 2 element exist"<<endl; } return 0; }
Output:
There are 2 element exist