algoadvance

You are given an array nums consisting of distinct positive integers. We call an array “good” if for any two elements a and b (where a != b), the product a * b is not present in the array nums. Your task is to determine whether the given array is “good”.

Write a Python function to check if the array is good.

Clarifying Questions:

  1. Input Size: Are there any constraints on the size of the input array?
  2. Constraints on Values: Are the values in nums distinct and positive?
  3. Special Cases: Should we consider the behavior for very small arrays (like arrays with 0 or 1 elements)?

Assumptions based on common problem constraints:

Strategy:

  1. Generate All Possible Products: Given the constraints, generating all pairs and their products would be computationally expensive due to its O(n^2) complexity.
  2. Check Product Presence: We will use a set to store the values in nums for O(1) average time complexity check.
  3. Iterate Over Pairs: We will iterate over every unique pair (a, b) in nums and check if a * b exists in the set.

Time Complexity:

Let’s implement the solution step by step.

from typing import List

def is_good_array(nums: List[int]) -> bool:
    num_set = set(nums)
    n = len(nums)
    
    for i in range(n):
        for j in range(i + 1, n):
            product = nums[i] * nums[j]
            if product in num_set:
                return False
    return True

This code ensures that we iterate over every unique pair of elements in the array, check if their product already exists in the set, and return False immediately if it does. If no such product is found, the array is determined to be “good.”

Explanation:

  1. Initialization: We create a set num_set from the list nums to allow O(1) time complexity when checking for the presence of elements.
  2. Nested Loop: We use a nested loop to go through all unique pairs (nums[i], nums[j]) where i < j.
  3. Product Check: For each pair, we calculate the product nums[i] * nums[j] and check if it’s present in num_set.
  4. Return Result: If any product is found in the set, we return False. If we complete the loop without finding any such product, we return True.

Considering the potential size of the input and constraints, this approach will efficiently determine if the array is “good.”

Try our interview co-pilot at AlgoAdvance.com