We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Card Flipping Game

Number: 842

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

You are given two arrays, fronts and backs, representing the numbers printed on the front and back of n cards. Initially, every card is placed with the front side up. You can flip any number of cards. An integer is called "good" if it appears on the backside of at least one card and does not appear on any card’s front after you perform the flips. The goal is to find the smallest possible good integer obtainable by flipping some of the cards. If no good integer exists, return 0.

Key Insights

  • If a card has the same number on both sides, that number will always appear on the front regardless of flipping. These numbers can never be good.
  • Use a set to collect numbers from cards that are the same on both sides (banned numbers).
  • Any number that is not banned and appears in the union of the numbers on both sides is a candidate to be good.
  • The smallest candidate among these numbers is the answer.

Space and Time Complexity

Time Complexity: O(n + U), where n is the number of cards and U is the number of unique numbers (in the worst-case U is bounded by 2000).
Space Complexity: O(n + U) due to the storage used in the sets for banned and candidate numbers.

Solution

The approach is to first determine the "banned" numbers that occur on both sides of the same card (since these numbers will always be present on the front regardless of flipping). Next, we form the union of all numbers present in the fronts and backs arrays. A number is a valid candidate if it is not banned. Finally, we return the smallest candidate. If no valid candidate exists, we return 0.

We use sets as our primary data structure to quickly check membership (O(1) average time) and to efficiently form the union and banned sets. The algorithm iterates through the list of cards a couple of times (once to create the banned set and once to examine all possible candidates).

Code Solutions

# Python solution

def flipgame(fronts, backs):
    # Set for banned numbers: numbers that are same on both sides
    banned = set()
    n = len(fronts)
    
    # Build the banned set for cards that have the same number on both sides.
    for i in range(n):
        if fronts[i] == backs[i]:
            banned.add(fronts[i])
    
    # Use a set to hold all unique candidate numbers from both fronts and backs.
    candidates = set(fronts + backs)
    
    # Initialize the result with a large number.
    res = float('inf')
    
    # Find the smallest candidate that is not banned.
    for num in candidates:
        if num not in banned:
            res = min(res, num)
    
    # If result is not updated, return 0.
    return res if res != float('inf') else 0

# Example usage:
print(flipgame([1,2,4,4,7], [1,3,4,1,3]))  # Output: 2
print(flipgame([1], [1]))                   # Output: 0
← Back to All Questions