Bird
Raised Fist0

Identify the subtle bug in the following code snippet for Minimum Domino Rotations: ```python def minDominoRotations(A, B): def check(x): rotations_a = rotations_b = 0 for i in range(len(A)): if A[i] != x and B[i] != x: return -1 elif A[i] != x: rotations_a += 1 elif B[i] != x: rotations_b += 1 return min(rotations_a, rotations_b) rotations = check(A[0]) if rotations != -1: return rotations else: return check(B[0]) ```

medium🐞 Bug Identification Q7 of Q15
Greedy Algorithms - Minimum Domino Rotations
Identify the subtle bug in the following code snippet for Minimum Domino Rotations: ```python def minDominoRotations(A, B): def check(x): rotations_a = rotations_b = 0 for i in range(len(A)): if A[i] != x and B[i] != x: return -1 elif A[i] != x: rotations_a += 1 elif B[i] != x: rotations_b += 1 return min(rotations_a, rotations_b) rotations = check(A[0]) if rotations != -1: return rotations else: return check(B[0]) ```
AReturning -1 too late after checking all dominoes
BNot handling the case when both A[i] and B[i] equal candidate, causing overcounting
CNot checking all numbers from 1 to 6 as candidates
DUsing min(rotations_a, rotations_b) instead of max
Step-by-Step Solution
Solution:
  1. Step 1: Analyze rotation counting

    If both A[i] and B[i] equal candidate, no rotation needed, but code counts only one side.
  2. Step 2: Identify overcounting

    Code increments rotations_a or rotations_b exclusively, missing the case where no rotation is needed, potentially overcounting.
  3. Step 3: Understand impact

    This leads to incorrect minimal rotations calculation.
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    Overcounting rotations leads to incorrect minimal rotations [OK]
Quick Trick: Check if both sides equal candidate to avoid overcounting [OK]
Common Mistakes:
MISTAKES
  • Ignoring no-rotation cases when both sides match candidate
Trap Explanation:
PITFALL
  • Candidates overlook the no-rotation scenario causing subtle bugs.
Interviewer Note:
CONTEXT
  • Tests bug identification in rotation counting logic.
Master "Minimum Domino Rotations" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Greedy Algorithms Quizzes