Scale Engineer

Card Flipping Game

Med
#0776Time: O(2^n * n). There are `2^n` configurations. For each, we iterate through `n` cards to build the sets (O(n)) and then iterate through the down-facing numbers (at most `n`) to find the minimum good number (O(n)). Thus, the total time is O(2^n * n).Space: O(n). The sets `up_numbers` and `down_numbers` can store up to `n` elements each.
Data structures
ArrayHash Table

Prompt

You are given two 0-indexed integer arrays fronts and backs of length n, where the ith card has the positive integer fronts[i] printed on the front and backs[i] printed on the back. Initially, each card is placed on a table such that the front number is facing up and the other is facing down. You may flip over any number of cards (possibly zero).

After flipping the cards, an integer is considered good if it is facing down on some card and not facing up on any card.

Return the minimum possible good integer after flipping the cards. If there are no good integers, return 0.

 

Example 1:

Input: fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
Output: 2
Explanation:
If we flip the second card, the face up numbers are [1,3,4,4,7] and the face down are [1,2,4,1,3].
2 is the minimum good integer as it appears facing down but not facing up.
It can be shown that 2 is the minimum possible good integer obtainable after flipping some cards.

Example 2:

Input: fronts = [1], backs = [1]
Output: 0
Explanation:
There are no good integers no matter how we flip the cards, so we return 0.

 

Constraints:

  • n == fronts.length == backs.length
  • 1 <= n <= 1000
  • 1 <= fronts[i], backs[i] <= 2000

Approaches

3 approaches with complexity analysis and trade-offs.

This approach explores every possible combination of card flips. Since each of the n cards can either be in its original state or flipped, there are 2^n total configurations. For each configuration, we determine the set of numbers facing up and the set of numbers facing down. We then find the minimum number that is in the "down" set but not in the "up" set. The overall minimum across all 2^n configurations is the answer.

Algorithm

  • Initialize min_good to a very large value.
  • Loop through all integers mask from 0 to 2^n - 1.
    • Create an empty set up_numbers and down_numbers.
    • For each card j from 0 to n-1:
      • If the j-th bit of mask is set, it means flip card j. Add backs[j] to up_numbers and fronts[j] to down_numbers.
      • Otherwise, do not flip. Add fronts[j] to up_numbers and backs[j] to down_numbers.
    • Initialize current_min_good to a very large value.
    • For each num in down_numbers:
      • If num is not in up_numbers, update current_min_good = min(current_min_good, num).
    • Update min_good = min(min_good, current_min_good).
  • If min_good is still the large initial value, return 0. Otherwise, return min_good.

Walkthrough

We use a bitmask, an integer from 0 to 2^n - 1, to represent a specific configuration of flips. If the j-th bit is 0, card j is not flipped. If it's 1, card j is flipped. The algorithm iterates through all 2^n masks. For each mask, it constructs two sets: up_numbers and down_numbers. It iterates through each card j from 0 to n-1. Based on the j-th bit of the mask, it adds the appropriate fronts[j] or backs[j] to the up_numbers and down_numbers sets. After building the sets for a configuration, it finds the minimum "good" number for that specific configuration by iterating through all numbers in down_numbers and checking if they are absent from up_numbers. A global minimum is maintained and updated after processing each of the 2^n configurations. If no good number is ever found, we return 0.

import java.util.HashSet;import java.util.Set; class Solution {    public int flipgame(int[] fronts, int[] backs) {        int n = fronts.length;        int minGood = Integer.MAX_VALUE;         for (int i = 0; i < (1 << n); i++) { // Iterate through all 2^n flip combinations            Set<Integer> upNumbers = new HashSet<>();            Set<Integer> downNumbers = new HashSet<>();             for (int j = 0; j < n; j++) {                if ((i >> j & 1) == 1) { // Card j is flipped                    upNumbers.add(backs[j]);                    downNumbers.add(fronts[j]);                } else { // Card j is not flipped                    upNumbers.add(fronts[j]);                    downNumbers.add(backs[j]);                }            }             int currentMinGood = Integer.MAX_VALUE;            for (int num : downNumbers) {                if (!upNumbers.contains(num)) {                    currentMinGood = Math.min(currentMinGood, num);                }            }            minGood = Math.min(minGood, currentMinGood);        }         return minGood == Integer.MAX_VALUE ? 0 : minGood;    }}

Complexity

Time

O(2^n * n). There are `2^n` configurations. For each, we iterate through `n` cards to build the sets (O(n)) and then iterate through the down-facing numbers (at most `n`) to find the minimum good number (O(n)). Thus, the total time is O(2^n * n).

Space

O(n). The sets `up_numbers` and `down_numbers` can store up to `n` elements each.

Trade-offs

Pros

  • Conceptually simple, as it directly models the problem statement by trying all possibilities.

Cons

  • Extremely inefficient. The exponential time complexity makes it infeasible for the given constraints (n up to 1000). It will result in a "Time Limit Exceeded" error.

Solutions

public class Solution {    public int Flipgame(int[] fronts, int[] backs) {        var s = new HashSet < int > ();        int n = fronts.Length;        for (int i = 0; i < n; ++i) {            if (fronts[i] == backs[i]) {                s.Add(fronts[i]);            }        }        int ans = 9999;        for (int i = 0; i < n; ++i) {            if (!s.Contains(fronts[i])) {                ans = Math.Min(ans, fronts[i]);            }            if (!s.Contains(backs[i])) {                ans = Math.Min(ans, backs[i]);            }        }        return ans % 9999;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem