Eeyore's House

TIP102 Unit 1 Session 2 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Arrays, Nested Loops, Modulo Operation

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the function?

  • A: The input consists of two integer arrays pile1 and pile2, and a positive integer k.

• Q: What is the expected output of the function?

  • A: The function should return the number of good pairs (i, j) where pile1[i] is divisible by pile2[j] * k.

• Q: How is a good pair defined?

  • A: A pair (i, j) is called good if pile1[i] % (pile2[j] * k) == 0.

• Q: What should the function return if there are no good pairs?

  • A: The function should return 0 if no good pairs are found.

• Q: Can the arrays be empty or have elements that are zero?

  • A: The problem assumes the arrays contain positive integers, as stick lengths cannot be zero. Either pile may be empty, in which case there are no good pairs and the function returns 0.

• The function good_pairs() should take two integer arrays pile1 and pile2, and a positive integer k, returning the number of good pairs. A pair (i, j) is good if pile1[i] is divisible by pile2[j] * k.

HAPPY CASE
Input: pile1 = [1, 3, 4], pile2 = [1, 3, 4], k = 1
Expected Output: 5

Input: pile1 = [1, 2, 4, 12], pile2 = [2, 4], k = 3
Expected Output: 2

EDGE CASE
Input: pile1 = [2, 4, 6], pile2 = [1, 1, 1], k = 2
Expected Output: 9

Input: pile1 = [], pile2 = [1, 2, 3], k = 1
Expected Output: 0

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Iterate through each stick in pile1 and for each stick, iterate through each stick in pile2. Check if pile1[i] is divisible by pile2[j] * k. Count the number of such good pairs.

1. Initialize a counter `count` to 0.
2. Iterate through each stick in `pile1` using index `i`.
3. For each stick in `pile1`, iterate through each stick in `pile2` using index `j`.
4. Check if `pile1[i]` is divisible by `pile2[j] * k`.
5. If the condition is met, increment `count`.
6. Return the total `count` of good pairs.

⚠️ Common Mistakes

• Forgetting to handle empty arrays.
• Incorrectly checking the divisibility condition.

I-mplement

Implement the code to solve the algorithm.

def good_pairs(pile1, pile2, k):
    # Initialize the counter for good pairs
    count = 0
    
    # Iterate through each stick in pile1
    for i in range(len(pile1)):
        # Iterate through each stick in pile2
        for j in range(len(pile2)):
            # Check if pile1[i] is divisible by pile2[j] * k
            if pile1[i] % (pile2[j] * k) == 0:
                # Increment the counter if the condition is met
                count += 1
    
    # Return the total number of good pairs
    return count