product of array 0(n) time complexity if input is all o's TC=0(n2)
class Solution {
public static void main(String[] args) {
// Test Case 1: No zeros in the input array
int[] nums1 = {1, 2, 3, 4};
// Test Case 2: One zero in the input array
int[] nums2 = {1, 2, 0, 4};
// Create an instance of the Solution class
Solution solution = new Solution();
// Process Test Case 1
System.out.println("Test Case 1:");
System.out.println("Input Array: ");
for (int num : nums1) {
System.out.print(num + " ");
}
int[] result1 = solution.productExceptSelf(nums1);
System.out.println("\nProduct Except Self:");
for (int num : result1) {
System.out.print(num + " ");
}
// Process Test Case 2
System.out.println("\n\nTest Case 2:");
System.out.println("Input Array: ");
for (int num : nums2) {
System.out.print(num + " ");
}
int[] result2 = solution.productExceptSelf(nums2);
System.out.println("\nProduct Except Self:");
for (int num : result2) {
System.out.print(num + " ");
}
// Example output:
// Test Case 1:
// Input Array:
// 1 2 3 4
// Product Except Self:
// 24 12 8 6
//
// Test Case 2:
// Input Array:
// 1 2 0 4
// Product Except Self:
// 0 0 8 0
}
public int[] productExceptSelf(int[] nums) {
int len = nums.length; // Length of the input array
int[] answer = new int[len]; // Array to store the result
int res = 1; // Variable to store the product of all elements
int store = 1; // Variable to store the product excluding the current element (for zeros)
// Step 1: Calculate the product of all elements in the array
for (int i = 0; i < len; i++) {
res = res * nums[i];
}
// Store the total product to use later
int rewind = res;
// Step 2: Populate the result array
for (int i = 0; i < len; i++) {
// If the current element is zero
if (nums[i] == 0) {
// Calculate the product of all elements excluding the current one
for (int j = 0; j < len; j++) {
if (i == j) {
// Skip the current index
continue;
} else {
store *= nums[j]; // Multiply all other elements
}
}
answer[i] = store; // Store the calculated product for this index
} else {
// If the current element is non-zero, use division
answer[i] = res / nums[i]; // Divide the total product by the current element
res = rewind; // Reset `res` to the original total product
}
}
// Step 3: Return the final result array
return answer;
}
}
Comments
Post a Comment