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

Sign of the Product of an Array

Number: 1950

Difficulty: Easy

Paid? No

Companies: Meta, Microsoft, Google

Problem Description

You are given an integer array nums. Instead of calculating the actual product of all elements (which could be very large), determine its sign. Implement a function signFunc(x) that returns 1 if x is positive, -1 if x is negative, and 0 if x is zero. The goal is to return signFunc(product) for the product of the nums array.

Key Insights

  • If any element in the array is zero, the entire product is zero.
  • The product's sign only depends on the number of negative numbers:
    • An even count of negative numbers results in a positive product.
    • An odd count of negative numbers results in a negative product.
  • No need to multiply the numbers since we only care about sign.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in the array, as we iterate through it once.
Space Complexity: O(1) since only a few extra variables are used regardless of input size.

Solution

We iterate through the array and check for the following:

  1. If any element is zero, we immediately return 0 because the product will be zero.
  2. Otherwise, count the number of negative numbers.
    • If the count of negative numbers is odd, the sign of the product is -1.
    • If the count of negative numbers is even, the sign of the product is 1. This approach avoids potential overflow issues and unnecessary multiplication.

Code Solutions

# Python solution with detailed comments

def arraySign(nums):
    # Initialize count for negative numbers
    negative_count = 0
    
    # Iterate through the list of numbers
    for num in nums:
        # If any number is zero, the product is zero
        if num == 0:
            return 0
        # Count the negative numbers
        if num < 0:
            negative_count += 1

    # If the count of negative numbers is odd, product is negative; otherwise, it's positive
    return -1 if negative_count % 2 != 0 else 1

# Example usage:
# result = arraySign([-1,-2,-3,-4,3,2,1])
# print(result)  # Output: 1
← Back to All Questions