मान लीजिए कुछ लोग फ्रेंड रिक्वेस्ट करेंगे। हम उनकी उम्र जानते हैं, ये ages[i] में संग्रहीत हैं। तो यह दर्शाता है कि i-th व्यक्ति की उम्र। अब A व्यक्ति B को फ्रेंड रिक्वेस्ट नहीं करेगा (B != A) यदि निम्नलिखित में से कोई भी शर्त सत्य है -
- age[B] <= 0.5 * age[A] + 7
- age[B] > age[A]
- age[B] > 100 && age[A] < 100
अन्यथा, A, B को फ्रेंड रिक्वेस्ट करेगा। आप मान सकते हैं कि यदि A, B को रिक्वेस्ट करता है, तो B आवश्यक रूप से A को रिक्वेस्ट नहीं करता। और साथ ही, लोग खुद को फ्रेंड रिक्वेस्ट नहीं करेंगे। तो हमें यह पता लगाना है कि कुल कितनी फ्रेंड रिक्वेस्ट की जाती हैं?
मान लीजिए यदि उम्र सरणी [16,17,18] जैसी है, तो परिणाम 2 होगा, क्योंकि रिक्वेस्ट 17 -> 16, 18 -> 17 होंगी।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- आकार 1000 की एक सरणी बकेट परिभाषित करें, फिर ages सरणी के तत्वों की आवृत्ति को बकेट में संग्रहीत करें।
- फिर बकेट तत्वों का संचयी योग ढूंढें और संग्रहीत करें, बकेट में
- ret := 0
- i को 0 से ages सरणी के आकार - 1 की रेंज में
- x := ages[i], y := (ages[i] / 2) + 7
- यदि x >= y, तो
- ret := bucket[x] - bucket[y]
- यदि bucket[x] - bucket[y] शून्येतर है, तो ret को 1 से घटाएं
- ret लौटाएं।
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numFriendRequests(vector<int>& ages) {
vector <int> bucket(1000);
for(int i = 0; i < ages.size(); i++){
bucket[ages[i]]++;
}
for(int i = 1; i < 1000; i++)bucket[i] += bucket[i - 1];
int ret = 0;
for(int i = 0; i < ages.size(); i++){
int x = ages[i];
int y = ((ages[i]) / 2) + 7;
if(x >= y){
ret += (bucket[x] - bucket[y]);
if((bucket[x] - bucket[y]))
ret--;
}
}
return ret;
}
};
main(){
vector<int> v1 = {16, 17, 18};
Solution ob;
cout << (ob.numFriendRequests(v1));
}
इनपुट
[16,17,18]
आउटपुट
2