मान लीजिए एक टेबल पर N कार्ड हैं, जिनके दोनों तरफ एक सकारात्मक पूर्णांक प्रिंटेड है (संभवतः अलग)। हमें किसी भी संख्या में कार्ड्स को फ्लिप करना है, और उसके बाद हम एक कार्ड चुनते हैं। यदि चुने गए कार्ड के पीछे की तरफ संख्या X किसी भी कार्ड के सामने नहीं है, तो संख्या X को अच्छा माना जाता है। हमें सबसे छोटी संख्या ढूंढनी है जो अच्छी है? जब कोई संख्या अच्छी नहीं है, तो 0 लौटाएं। यहां, fronts[i] और backs[i] कार्ड i के सामने और पीछे की तरफ की संख्या को दर्शाते हैं। एक फ्लिप सामने और पीछे की संख्याओं को स्वैप कर देगा, इसलिए सामने का मान अब पीछे है और इसके विपरीत।
तो यदि इनपुट fronts = [1,2,4,4,7] और backs = [1,3,4,1,3] जैसा है, तो आउटपुट 2 होगा। तो यदि हम दूसरे कार्ड को फ्लिप करते हैं, तो सामने का मान [1,3,4,4,7] होगा, और पीछे [1,2,4,1,3] होगा। हम दूसरे कार्ड को चुनेंगे, जिसके पीछे संख्या 2 है, और यह किसी भी कार्ड के सामने नहीं है, इसलिए 2 एक अच्छी संख्या है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक सेट s परिभाषित करें, n := fronts का आकार, ret := inf
- i को 0 से n - 1 की रेंज में
- यदि fronts[i] = back[i], तो fronts[i] को s में डालें
- i को 0 से n - 1 की रेंज में
- यदि fronts[i] सेट में है तो ret := ret और fronts[i] का न्यूनतम
- i को 0 से n - 1 की रेंज में
- यदि backs[i] सेट में नहीं है तो ret := ret और backs[i] का न्यूनतम
- ret = inf होने पर 0 लौटाएं, अन्यथा ret।
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int flipgame(vector<int>& fronts, vector<int>& backs) {
set <int> s;
int n = fronts.size();
int ret = INT_MAX;
for(int i = 0; i < n; i++){
if(fronts[i] == backs[i])s.insert(fronts[i]);
}
for(int i = 0; i <n; i++ ){
if(s.count(fronts[i]) == 0) ret = min(ret, fronts[i]);
}
for(int i = 0; i <n; i++ ){
if(s.count(backs[i]) == 0) ret = min(ret, backs[i]);
}
return ret == INT_MAX? 0 : ret;
}
};
main(){
vector<int> v1 = {1,2,4,4,7};
vector<int> v2 = {1,3,4,1,3};
Solution ob;
cout << (ob.flipgame(v1, v2));
}
इनपुट
[1,2,4,4,7] [1,3,4,1,3]
आउटपुट
2
