Sign of the Product of an Array
Leetcode Daily Challenge (2nd May, 2023)
Problem Statement:-
There is a function signFunc(x) that returns:
1ifxis positive.-1ifxis negative.0ifxis equal to0.
You are given an integer array nums. Let product be the product of all values in the array nums.
Return signFunc(product).
Link: https://leetcode.com/problems/sign-of-the-product-of-an-array/description/
Problem Explanation with examples:-
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
Intuition:-
If we have the count of negative numbers in the array, we can easily determine the sign of the product.
If the count is even, the product is positive. If the count is odd, the product is negative.
If the array contains a zero, the product is zero.
Solution:-
Initialize a variable nc to 0. This variable will store the count of negative numbers in the array.
Iterate over the array. If the current element is negative, increment nc by 1.
If the current element is zero, return 0.
After the loop completes, return 1 if nc is even, else return -1.
Code:-
JAVA Solution
class Solution {
public int arraySign(int[] nums) {
int nc = 0;
for (int i : nums) {
if (i < 0)
nc += 1;
if (i == 0)
return 0;
}
return (nc % 2 == 0) ? 1 : -1;
}
}
Python Solution
class Solution:
def arraySign(self, nums: List[int]) -> int:
nc = 0
for i in nums:
if i < 0:
nc += 1
if i == 0:
return 0
return 1 if nc%2==0 else -1
Complexity Analysis:-
TIME:-
The time complexity is O(n) where n is the length of the array. We iterate over the array once.
SPACE:-
The space complexity is O(1) since we do not use any extra space.