Sponsored
Sponsored
This approach uses a Hash Set to store elements as we iterate through the array. For each element, we check if its double or half (only if it's even) exists in the set. This allows for efficient lookup and insertion operations.
Time Complexity: O(n), because we iterate through the array once and do constant time operations for each element.
Space Complexity: O(1), since the hash set size is fixed regardless of input size.
1#include <stdbool.h>
2#include <stdlib.h>
3
4bool checkIfExist(int* arr, int arrSize) {
5 bool *hashMap = (bool*)calloc(2001, sizeof(bool)); // Hash set to store the presence of numbers
6 for (int i = 0; i < arrSize; i++) {
7 if (arr[i] >= -1000 && arr[i] <= 1000) {
8 if (arr[i] % 2 == 0 && hashMap[(arr[i] / 2) + 1000]) {
9 free(hashMap);
10 return true;
11 }
12 if (hashMap[(arr[i] * 2) + 1000]) {
13 free(hashMap);
14 return true;
15 }
16 hashMap[arr[i] + 1000] = true;
17 }
18 }
19 free(hashMap);
20 return false;
21}This C solution allocates a fixed-size boolean array to act as a hash set for values that have been seen. For each number, it checks if twice the number or half (if even) exists by using offset indexing for negative values.
This approach involves sorting the array first. Once sorted, we can use two pointers to find if there exist indices i and j such that one element is twice the other. Sorting helps to systematically check this condition.
Time Complexity: O(n log n) for sorting, then O(n^2) for the two-pointer search.
Space Complexity: O(1) as it sorts in place.
1#include <algorithm>
using namespace std;
bool checkIfExist(vector<int>& arr) {
sort(arr.begin(), arr.end());
for (int i = 0; i < arr.size(); i++) {
for (int j = i + 1; j < arr.size() && arr[j] <= 2 * arr[i]; j++) {
if (arr[j] == 2 * arr[i] || arr[i] == 2 * arr[j]) {
return true;
}
}
}
return false;
}This C++ implementation sorts the array and uses the two-pointer technique to check pairs of elements, taking advantage of the sorted order to efficiently check conditions.