Sponsored
Sponsored
This approach involves using a hash map (or dictionary) to store the frequency of each integer in the array. Once frequencies are calculated, iterate through the map to find integers whose value is equal to their frequency, and track the maximum of such values.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), since the frequency array is of constant size (501).
In this C solution, we use an array freq of size 501 to capture the frequency of numbers from 1 to 500. We then iterate over the original array updating our frequency array. Finally, we search for the maximum lucky number by checking if the frequency matches the number itself.
This approach involves using an array to directly track the frequency of each integer. By using an array of fixed size, we can avoid using a hash map or dictionary, which optimizes space usage when the domain of the input elements is known.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), using a constant-size array.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5int findLucky(vector<int>& arr) {
6 int freq[501] = {0};
7 for (int num : arr) {
8 freq[num]++;
9 }
10 int maxLucky = -1;
11 for (int i = 1; i <= 500; i++) {
12 if (freq[i] == i && i > maxLucky) {
13 maxLucky = i;
14 }
15 }
16 return maxLucky;
17}
18
19int main() {
20 vector<int> arr = {2, 2, 3, 4};
21 cout << findLucky(arr) << endl;
22 return 0;
23}This C++ solution uses a simple integer array to store frequencies, thus removing the need for hash maps. We store frequencies and verify the constraints directly in a fixed-size array.