Prefix Sum XI

Prefix Sum together with Suffix Product. No need to use Big Integer for this problem (which would slow down the solution considerably), you can just use long and whenever the suffix product gets greater than the max prefix sum, you know that from that point onwards you won't have a possible solution, hence just keep setting the suffix product to -1. Also, the fact that zero isn't allowed as a potential array element simplifies the solution a bit. Code is down below, cheers, ACC.

Find the Smallest Balanced Index - LeetCode

You are given an integer array nums.

An index i is balanced if the sum of elements strictly to the left of i equals the product of elements strictly to the right of i.

If there are no elements to the left, the sum is considered as 0. Similarly, if there are no elements to the right, the product is considered as 1.

Return an integer denoting the smallest balanced index. If no balanced index exists, return -1.

 

Example 1:

Input: nums = [2,1,2]

Output: 1

Explanation:

For index i = 1:

• Left sum = nums[0] = 2
• Right product = nums[2] = 2
• Since the left sum equals the right product, index 1 is balanced.

No smaller index satisfies the condition, so the answer is 1.

Example 2:

Input: nums = [2,8,2,2,5]

Output: 2

Explanation:

For index i = 2:

• Left sum = 2 + 8 = 10
• Right product = 2 * 5 = 10
• Since the left sum equals the right product, index 2 is balanced.

No smaller index satisfies the condition, so the answer is 2.

Example 3:

Input: nums = [1]

Output: -1

For index i = 0:

• The left side is empty, so the left sum is 0.
• The right side is empty, so the right product is 1.
• Since the left sum does not equal the right product, index 0 is not balanced.

Therefore, no balanced index exists and the answer is -1.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

public class Solution {
    public int SmallestBalancedIndex(int[] nums)
    {
        long[] prefixSum = new long[nums.Length];

        prefixSum[0] = 0;
        for (int i = 1; i < prefixSum.Length; i++)
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];

        long[] suffixProduct = new long[nums.Length];
        suffixProduct[suffixProduct.Length - 1] = 1;

        for (int i = suffixProduct.Length - 2; i >= 0; i--)
        {
            long product = suffixProduct[i + 1] * nums[i + 1];
            if (product > prefixSum[prefixSum.Length - 1] || product < 0) product = -1;
            suffixProduct[i] = product;
        }

        for (int i = 0; i < nums.Length; i++)
            if (prefixSum[i] == suffixProduct[i]) return i;

        return -1;
    }
}