prefix sum – My Programming Notes

Tag Archives: prefix sum

C# || How To Find Product Of Array Except Self Using C#

November 26, 2021 admin No comments

The following is a module with functions which demonstrates how to find the product of an array except itself using C#.

1. Product Except Self – Problem Statement

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4] Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]

2. Product Except Self – Solution

The following is a solution which demonstrates how to find the product of an array except itself.

In this solution, the product for result[i] is calculated by scanning the input array, and multiplying the numbers that come before the current i, and the numbers that come after the current i.

First, the running product of the numbers that come before the current i is calculated by scanning the array starting from the beginning (prefix).

Then, the running product of the numbers that come after the current i is calculated by scanning the array starting from the end (suffix).





		
		
			2. Product Except Self - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 26, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find product of array except self
// ============================================================================
public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        var result = new int[nums.Length];

        // Prefix
        var runningPrefix = 1;
        for (int index = 0; index < nums.Length; ++index) {
            result[index] = runningPrefix;
            runningPrefix *= nums[index];
        }

        // Suffix
        var runningSufix = 1;
        for (int index = nums.Length - 1; index >= 0; --index) {
            result[index] *= runningSufix;
            runningSufix *= nums[index];
        }
        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 26, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find product of array except self
// ============================================================================
public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        var result = new int[nums.Length];
 
        // Prefix
        var runningPrefix = 1;
        for (int index = 0; index < nums.Length; ++index) {
            result[index] = runningPrefix;
            runningPrefix *= nums[index];
        }
 
        // Suffix
        var runningSufix = 1;
        for (int index = nums.Length - 1; index >= 0; --index) {
            result[index] *= runningSufix;
            runningSufix *= nums[index];
        }
        return result;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[24,12,8,6] [0,0,9,0,0]

Tag Archives: prefix sum

C# || How To Find Product Of Array Except Self Using C#

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories