Given a 3-Dimensional array of integers A[L][R][C], where L, R, and C are dimensions of the array (Layer, Row, Column). Find prefix sum 3d array for it.
Let Prefix sum 3d array be prefix[L][R][C]. Here prefix[k][i][j] gives sum of all integers between prefix[0][0][0] and prefix[k][i][j] (including both).
Example:
Input:
array[L][R][C] = {
{{2, 2, 2, 2}, //Layer 1
{2, 2, 2, 2},
{2, 2, 2, 2},
{2, 2, 2, 2}},
{{2, 2, 2, 2}, //Layer 2
{2, 2, 2, 2},
{2, 2, 2, 2},
{2, 2, 2, 2}},
{{2, 2, 2, 2}, //Layer 3
{2, 2, 2, 2},
{2, 2, 2, 2},
{2, 2, 2, 2}},
{{2, 2, 2, 2}, //Layer 4
{2, 2, 2, 2},
{2, 2, 2, 2},
{2, 2, 2, 2}}
};
Output:
Layer 1:
2 4 6 8
4 8 12 16
6 12 18 24
8 16 24 32
Layer 2:
4 8 12 16
8 16 24 32
12 24 36 48
16 32 48 64
Layer 3:
6 12 18 24
12 24 36 48
18 36 54 72
24 48 72 96
Layer 4:
8 16 24 32
16 32 48 64
24 48 72 96
32 64 96 128
Explanation:
Step 0:
Element at (0,0,0) is directly filled.
prefix[0][0][0] = array[0][0][0]
Step 1:
Fill cells of three edges (parallel to x, y, z-axis and made up using cells) using prefix sum on the one-dimensional array.
check this article for 1d prefix sum: prefix sum for 1d array
These edges have common element prefix[0][0][0].
Step 2:
Fill cells of three sides (parallel to xy, yz, zx-plane and made up using cells) using prefix sum on the two-dimensional array.
check this article for 2d prefix sum: prefix sum for 2d array
These sides have common element prefix[0][0][0].
Step 3:
Fill all remaining cells using the general formula.
prefix[k][i][j] = array[k][i][j]
+ prefix[k - 1][i][j]
+ prefix[k][i - 1][j]
+ prefix[k][i][j - 1]
- prefix[k - 1][i - 1][j]
- prefix[k][i - 1][j - 1]
- prefix[k - 1][i][j - 1]
+ prefix[k - 1][i - 1][j - 1];
Implimentation:
C++ Implimentation:
// C++ program to calculate prefix sum of 3d array
#include <bits/stdc++.h>
using namespace std;
// Declaring size of the array
#define L 4 //Layer
#define R 4 //Row
#define C 4 //Column
// Calculating prefix
void prefixSum3d(int array[L][R][C])
{
int prefix[L][R][C];
prefix[0][0][0] = array[0][0][0];
// Step 1: Filling the first row,column, and pile of ceils.
// Using prefix sum of 1d array
for (int i = 1; i < L; i++)
prefix[i][0][0] = prefix[i - 1][0][0] + array[i][0][0];
for (int i = 1; i < R; i++)
prefix[0][i][0] = prefix[0][i - 1][0] + array[0][i][0];
for (int i = 1; i < C; i++)
prefix[0][0][i] = prefix[0][0][i - 1] + array[0][0][i];
// Step 2: Filling the cells of sides(made up using cells)
// which have common element array[0][0][0].
// using prefix sum on 2d array
for (int k = 1; k < L; k++)
{
for (int i = 1; i < R; i++)
{
prefix[k][i][0] = array[k][i][0]
+ prefix[k - 1][i][0] + prefix[k][i - 1][0]
- prefix[k - 1][i - 1][0];
}
}
for (int i = 1; i < R; i++)
{
for (int j = 1; j < C; j++)
{
prefix[0][i][j] = array[0][i][j]
+ prefix[0][i - 1][j] + prefix[0][i][j - 1]
- prefix[0][i - 1][j - 1];
}
}
for (int j = 1; j < C; j++)
{
for (int k = 1; k < L; k++)
{
prefix[k][0][j] = array[k][0][j]
+ prefix[k - 1][0][j] + prefix[k][0][j - 1]
- prefix[k - 1][0][j - 1];
}
}
// Step 3: Filling value in remaining cells using formula
for (int k = 1; k < L; k++)
{
for (int i = 1; i < R; i++)
{
for (int j = 1; j < C; j++)
{
prefix[k][i][j] = array[k][i][j]
+ prefix[k - 1][i][j]
+ prefix[k][i - 1][j]
+ prefix[k][i][j - 1]
- prefix[k - 1][i - 1][j]
- prefix[k][i - 1][j - 1]
- prefix[k - 1][i][j - 1]
+ prefix[k - 1][i - 1][j - 1];
}
}
}
// Displaying final prefix sum of array
cout << "prefix sum is:" << endl << endl;
for (int k = 0; k < L; k++)
{
cout << "Layer " << k + 1 << ":" << endl;
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
cout << prefix[k][i][j] << " ";
}
cout << endl;
}
cout << endl;
}
}
// Driver program to test above function
int main()
{
int array[L][R][C] = {
{{2, 2, 2, 2}, //Layer 1
{2, 2, 2, 2},
{2, 2, 2, 2},
{2, 2, 2, 2}},
{{2, 2, 2, 2}, //Layer 2
{2, 2, 2, 2},
{2, 2, 2, 2},
{2, 2, 2, 2}},
{{2, 2, 2, 2}, //Layer 3
{2, 2, 2, 2},
{2, 2, 2, 2},
{2, 2, 2, 2}},
{{2, 2, 2, 2}, //Layer 4
{2, 2, 2, 2},
{2, 2, 2, 2},
{2, 2, 2, 2}}
};
prefixSum3d(array);
return 0;
}
python code for it:
# python program to calculate prefix sum of 3d array
# Declaring size of the array
L = 4 # Layer
R = 4 # Row
C = 4 # Column
# Calculating prefix
def prefixSum3d(array):
prefix = [[[0 for a in range(C)]
for b in range(R)]
for d in range(L)]
prefix[0][0][0] = array[0][0][0]
# Step 1: Filling the first row,column, and pile of ceils.
# Using prefix sum of 1d array
for i in range(1, L):
prefix[i][0][0] = prefix[i - 1][0][0] + array[i][0][0]
for i in range(1, R):
prefix[0][i][0] = prefix[0][i - 1][0] + array[0][i][0]
for i in range(1, C):
prefix[0][0][i] = prefix[0][0][i - 1] + array[0][0][i]
# Step 2: Filling the cells of sides(made up using cells)
# which have common element A[0][0][0].
# using prefix sum on 2d array
for k in range(1, L):
for i in range(1, R):
prefix[k][i][0] = (array[k][i][0]
+ prefix[k - 1][i][0] + prefix[k][i - 1][0]
- prefix[k - 1][i - 1][0])
for i in range(1, R):
for j in range(1, C):
prefix[0][i][j] = (array[0][i][j]
+ prefix[0][i - 1][j] + prefix[0][i][j - 1]
- prefix[0][i - 1][j - 1])
for j in range(1, C):
for k in range(1, L):
prefix[k][0][j] = (array[k][0][j]
+ prefix[k - 1][0][j] + prefix[k][0][j - 1]
- prefix[k - 1][0][j - 1])
# Step 3: Filling value in remaining cells using formula
for k in range(1, L):
for i in range(1, R):
for j in range(1, C):
prefix[k][i][j] = (array[k][i][j]
+ prefix[k - 1][i][j]
+ prefix[k][i - 1][j]
+ prefix[k][i][j - 1]
- prefix[k - 1][i - 1][j]
- prefix[k][i - 1][j - 1]
- prefix[k - 1][i][j - 1]
+ prefix[k - 1][i - 1][j - 1])
# Displaying final prefix sum of array
print("prefix sum is:")
for k in range(L):
print("Layer", k+1, ":")
for i in range(R):
for j in range(C):
print(prefix[k][i][j], end=' ')
print()
print()
# Driver program to test above function
array = [
[[2, 2, 2, 2], # Layer 1
[2, 2, 2, 2],
[2, 2, 2, 2],
[2, 2, 2, 2]],
[[2, 2, 2, 2], # Layer 2
[2, 2, 2, 2],
[2, 2, 2, 2],
[2, 2, 2, 2]],
[[2, 2, 2, 2], # Layer 3
[2, 2, 2, 2],
[2, 2, 2, 2],
[2, 2, 2, 2]],
[[2, 2, 2, 2], # Layer 4
[2, 2, 2, 2],
[2, 2, 2, 2],
[2, 2, 2, 2]]
]
prefixSum3d(array)
Time Complexity: O(L*R*C)
Auxiliary Space: O(L*R*C)
Find the type of Quadrilateral with given 4 points of the quadrilateral here.
0 Comments
If you have any doubt let me know.