Card Flipping Game in C++

Suppose on a table are N cards, with a positive integer printed on both side of each card (possibly different). We have to flip any number of cards, and after we choose one card. If the number X on the back side of the chosen card is not on the front of any card, then the number X is known as good. We have to find the smallest number that is good? When no number is good, return 0. Here, fronts[i] and backs[i] represent the number on the front and back side of card i. A flip will swap the front and back numbers, so the value on the front is now on the back and vice versa.

So if the input is like fronts = [1,2,4,4,7] and backs = [1,3,4,1,3], then the output will be 2. So if we flip the second card, the front value will be [1,3,4,4,7], and the backs will be [1,2,4,1,3]. We will choose the second card, which has number 2 on the back, and it is not on the front of any card, so 2 is a good number.

To solve this, we will follow these steps −

• define a set s, n := size of fronts, ret := inf
• for i in range 0 to n – 1
  • if fronts[i] = back[i], then insert fronts[i] into s
• for i in range 0 to n – 1
  • if fronts[i] in set then ret := minimum of ret and fronts[i]
• for i in range 0 to n – 1
  • if backs[i] not in set then ret := minimum of ret and backs[i]
• return 0 when ret = inf, otherwise ret.

Let us see the following implementation to get better understanding −

Example

 Live Demo

#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)); }

Input

[1,2,4,4,7] [1,3,4,1,3]

Output

2