343. Product Array Puzzle

Given an array of n integers, construct and print an array where each element at index i equals the product of every element of the original array except arr[i] - without using division anywhere.

Input: The first line contains an integer n. The second line contains n space-separated integers, each between -50 and 50. Output: Print n space-separated integers, where each is the product of all elements except the one at that index.

1 <= n <= 12, -50 <= arr[i] <= 50

This approach handles ZEROS in the input completely naturally, with no special-casing needed at all - a division-based approach would need extra logic to handle a zero (or multiple zeros) in the array correctly, which is exactly the trap this no-division constraint avoids.

For every position in an array, compute the product of every OTHER number in the array (excluding just that one position) - without ever using division. Brute force: For every position, multiply together every OTHER element directly with a nested loop - this costs O(n²), too slow for large arrays, and doesn't showcase the intended prefix/suffix insight. Optimised: Rather than recomputing the whole product from scratch for every position, precomputing prefix products and suffix products ONCE each (two simple linear passes) lets you answer every position's 'product of everything else' in O(1) per position, by simply combining its own prefix and suffix values.

First fill the output array itself with prefix products in a single left-to-right pass (output[i] = product of everything before i), exactly as before but written directly into the answer array instead of a separate one. Then do a single right-to-left pass carrying just one running scalar variable representing the suffix product seen so far, multiplying it into output[i] and updating the running variable as you go. This reuses the output array for the prefix pass and only needs one extra number for the suffix, eliminating the second full-length array entirely while staying linear time and never dividing. Time: O(n) Space: O(1) extra (excluding output array)

For each index i, run an inner loop over every other index j (j != i) and multiply together arr[j] to build the product of all elements except arr[i], storing the result at output[i]. This directly implements the definition without ever using division, but recomputes overlapping products from scratch for every i, giving quadratic time. With n at most 12 this is perfectly fast in practice, but it does not scale. Time: O(n^2) Space: O(1) extra (excluding output array)

Build a prefix array where prefix[i] holds the product of all elements strictly before index i, and a suffix array where suffix[i] holds the product of all elements strictly after index i (both computable with one left-to-right and one right-to-left pass respectively). Then the answer at each index is simply prefix[i] * suffix[i], computed with a third pass. This never divides anything and cuts the work down to linear time, at the cost of two extra full-length arrays. Time: O(n) Space: O(n)

1. Build a 'prefix product' array: at each position, the product of every element BEFORE it. 2. Build a 'suffix product' array: at each position, the product of every element AFTER it. 3. For each position, multiply its prefix product by its suffix product - this gives the product of everything EXCEPT that position, with no division ever needed.

Time: O(n) - two precomputation passes plus one final combination pass, all linear. Space: O(n), for the prefix and suffix product arrays (though this can be optimized down to O(1) extra space beyond the output array, by computing suffix products on the fly while reusing the output array for prefix products first).

n = 1 (the product of zero remaining elements is 1); the array containing one or more zero values, which the prefix/suffix-product approach must still handle correctly without division; n at its largest allowed value of 12.

Be ready to explain explicitly why division isn't used here (the problem statement forbids it, and it also elegantly avoids issues with zeros in the array, which division-based approaches would need special-casing for) - this no-division requirement is exactly why the prefix/suffix technique is the expected approach.