Teaching Kids Programming – Sign of the Product of an Array

Teaching Kids Programming: Videos on Data Structures and Algorithms

There is a function signFunc(x) that returns:

• 1 if x is positive.
• -1 if x is negative.
• 0 if x is equal to 0.

You are given an integer array nums. Let product be the product of all values in the array nums.

Return signFunc(product).

Example 1:
Input: nums = [-1,-2,-3,-4,3,2,1]
Output: 1
Explanation: The product of all values in the array is 144, and signFunc(144) = 1

Example 2:
Input: nums = [1,5,0,2,-3]
Output: 0
Explanation: The product of all values in the array is 0, and signFunc(0) = 0

Example 3:
Input: nums = [-1,1,-1,1,-1]
Output: -1
Explanation: The product of all values in the array is -1, and signFunc(-1) = -1

Constraints:
1 <= nums.length <= 1000
-100 <= nums[i] <= 100

Hints:
If there is a 0 in the array the answer is 0
To avoid overflow make all the negative numbers -1 and all positive numbers 1 and calculate the prod

Let’s define the Sgn Function:

1
2
3
4

def sgn(n):
  if n == 0:
    return 0
  return 1 if n > 0 else -1

def sgn(n):
  if n == 0:
    return 0
  return 1 if n > 0 else -1

Compute the Sgn Function of the Product

We can compute the product of all numbers in the array and then compute its sign value:

1
2
3
4
5
6

class Solution:
    def arraySign(self, nums: List[int]) -> int:
        x = 1
        for i in nums:
            x *= i
        return sgn(x)

class Solution:
    def arraySign(self, nums: List[int]) -> int:
        x = 1
        for i in nums:
            x *= i
        return sgn(x)

We can use the reduce from functools and feed it a lambda function of simple multiplication:

1
2
3

class Solution:
    def arraySign(self, nums: List[int]) -> int:
        return functools.sgn(reduce(lambda a, b: a * b, nums))

class Solution:
    def arraySign(self, nums: List[int]) -> int:
        return functools.sgn(reduce(lambda a, b: a * b, nums))

Compute the Sgn Function by Counting the number of Negative Numebers

If there is a zero, the produce will be zero. If there are even number of negative numbers, the product will be positive, otherwise, the product will be negative.

1
2
3
4
5
6
7
8
9

class Solution:
    def arraySign(self, nums: List[int]) -> int:
        neg = 0
        for i in nums:
            if i == 0:
                return 0
            if i < 0:
                neg += 1
        return 1 if neg & 1 == 0 else -1

class Solution:
    def arraySign(self, nums: List[int]) -> int:
        neg = 0
        for i in nums:
            if i == 0:
                return 0
            if i < 0:
                neg += 1
        return 1 if neg & 1 == 0 else -1

Both time complexity is O(N) and space complexity is O(1). However, the second approach is better and faster as it does not need to compute the actual product. And also it avoids the integer overflow as will be in some other programming languages e.g. C++.

See other implementations:

• GoLang: Sign of the Product of an Array
• Teaching Kids Programming – Sign of the Product of an Array

–EOF (The Ultimate Computing & Technology Blog) — <