Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

सरणी में दिए गए शर्त को पूरा करने वाले युग्मों की संख्या ज्ञात करने का C++ प्रोग्राम


मान लीजिए nums सरणी में n संख्याएँ दी गई हैं। हमें सरणी से दो संख्याओं का एक युग्म चुनना है, और शर्त यह है कि सरणी में उनकी स्थितियों का अंतर दोनों संख्याओं के योग के बराबर हो। दी गई सरणी से कुल n(n-1)/2 युग्म बन सकते हैं। हमें ऐसे युग्मों की कुल संख्या ज्ञात करनी है।

उदाहरण के लिए, यदि इनपुट है n = 8, nums = {4, 2, 1, 0, 1, 2, 3, 3}, तो आउटपुट 13 होगा।

सरणी में 13 ऐसे युग्म हो सकते हैं।

चरण

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

आकार n का सरणी vals परिभाषित करें
i := 0 से n-1 तक:
    vals[i] := i + 1 - nums[i]
vals सरणी को सॉर्ट करें
res := 0
i := 0 से n-1 तक:
    k := nums[i] + i + 1
    res := res + (vals में k से कम न होने वाले पहले मान की स्थिति - vals में k से अधिक न होने वाले पहले मान की स्थिति)
res लौटाएँ

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; int solve(int n, vector<int> nums){    vector<int> vals(n);    for( int i = 0; i < n; i++)       vals[i] = i + 1 - nums[i];    sort(vals.begin(), vals.end());    int res = 0;    for( int i = 0; i < n; i++ ) {       int k = nums[i] + i + 1;       res += upper_bound(vals.begin(), vals.end(), k) - lower_bound(vals.begin(), vals.end(), k);    }    return res; } int main() {   int n = 8; vector<int> nums = {4, 2, 1, 0, 1, 2, 3, 3}; cout<< solve(n, nums); return 0; }

इनपुट

8, {4, 2, 1, 0, 1, 2, 3, 3}

आउटपुट

13
  1. - ग्रिड में अधिकतम रोशन की जा सकने वाली सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए h × w आयाम का एक ग्रिड दिया गया है। ग्रिड की सेल्स में बल्ब या बाधाएँ हो सकती हैं। एक बल्ब सेल अपने दाएँ, बाएँ, ऊपर और नीचे की सेल्स को रोशन करता है और प्रकाश सेल्स के माध्यम से चमक सकता है जब तक कि कोई बाधा सेल प्रकाश को न रोक दे। बाधा सेल को रोशन नहीं किया जा सकता और यह बल्ब के प्रकाश क

  1. ग्रिड में रोशन सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम ग्रिड में रोशन सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए h × w आयाम का एक ग्रिड दिया गया है। ग्रिड की सेल्स में बल्ब या बाधाएँ हो सकती हैं। एक बल्ब सेल स्वयं और अपने दाएँ, बाएँ, ऊपर, नीचे की सेल्स को रोशन करता है। प्रकाश सेल्स के माध्यम से चमकता है जब तक कि कोई बाधा सेल इसे न रोक दे। बाधा सेल न तो रोशन हो सकती है और न ही प्रकाश को गुजरने देती ह

  1. दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स और m एज वाला एक अनभारित, निदेश रहित ग्राफ दिया गया है। ग्राफ में एक ब्रिज एज वह एज है जिसे हटाने से ग्राफ असंबद्ध हो जाता है। हमें दिए गए ग्राफ में ऐसी एज की संख्या ज्ञात करनी है। ग्राफ में समानांतर एज या सेल्फ-लूप नहीं हैं। उदाहरण के लिए, यदि इनपुट है n = 5, m = 6, edges = {{1