मान लीजिए कुछ लोग फ्रेंड रिक्वेस्ट करेंगे। हम उनकी उम्र जानते हैं, ये युगों में संग्रहीत हैं [i]। तो यह इंगित करता है कि ith व्यक्ति की आयु। अब ए ए नॉट फ्रेंड रिक्वेस्ट व्यक्ति बी (बी! =ए) यदि निम्न में से कोई भी शर्त सत्य है -
- आयु[बी] <=0.5 * आयु[ए] + 7
- उम्र[बी]>आयु[ए]
- आयु[बी]> 100 &&उम्र[ए] <100
अन्यथा, ए फ्रेंड रिक्वेस्ट बी करेगा। आप विचार कर सकते हैं कि अगर ए बी से अनुरोध करता है, बी जरूरी नहीं कि ए का अनुरोध करे। और साथ ही, लोग खुद से फ्रेंड रिक्वेस्ट नहीं करेंगे। तो हमें यह पता लगाना होगा कि कुल कितने मित्र अनुरोध किए गए हैं?
मान लीजिए यदि आयु सरणी [16,17,18] की तरह है, तो परिणाम 2 होगा, क्योंकि अनुरोध 17 -> 16, 18 -> 17 होंगे।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- 1000 आकार की एक सरणी बकेट परिभाषित करें, फिर आयु सरणी तत्वों की आवृत्ति को बकेट में संग्रहीत करें।
- फिर बकेट एलिमेंट के संचयी योग को बकेट में ढूंढें और स्टोर करें
- रिट:=0
- मैं के लिए 0 से आयु वर्ग के आकार के लिए - 1
- x :=उम्र [i], y :=(आयु[i] / 2) + 7
- यदि x>=y, तो
- रिट:=बकेट[x] - बकेट[y]
- अगर बकेट[x] - बकेट[y] शून्य नहीं है, तो रिट को 1 से घटाएं
- रिटर्न रिट।
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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