Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
Define a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinates (1,1,1) and the last block is defined by the coordinates (n,n,n). There are two types of queries.
UPDATE x y z W
Update the value of block (x,y,z) to W.
QUERY x1 y1 z1 x2 y2 z2
Calculate the sum of the values of blocks whose x coordinate is between x1 and x2 (inclusive), y coordinate between y1 and y2 (inclusive) and z coordinate between z1 and z2 (inclusive).
Function Description
Complete the cubeSum function in the editor below.
cubeSum has the following parameters: - *int n: the dimensions of the 3-d matrix - string operations[m]: the operations to perform
Returns
- int[]: the results of each QUERY operation
Input Format
The first line contains an integer T , the number of test-cases. T testcases follow.
For each test case, the first line contains two space-separated integers, n and m n the n * n * n matrix.
m defines the number of operations.
The next m lines will contain an operation either of these forms:
1. UPDATE x y z W
2. QUERY x1 y1 z1 x2 y2 z2
Sample Input
2
4 5
UPDATE 2 2 2 4
QUERY 1 1 1 3 3 3
UPDATE 1 1 1 23
QUERY 2 2 2 4 4 4
QUERY 1 1 1 3 3 3
2 4
UPDATE 2 2 2 1
QUERY 1 1 1 1 1 1
QUERY 1 1 1 2 2 2
QUERY 2 2 2 2 2 2
Sample Output
4
4
27
0
1
1
Explanation
In the first test case, there is a cube of 4 * 4 * 4 and there are 5 queries. Initially all the cells (1,1,1) to (4,4,4) are 0.
UPDATE 2 2 2 4 makes the cell (2,2,2) = 4
QUERY 1 1 1 3 3 3. As (2,2,2) is updated to 4 and the rest are all 0. The answer to this query is 4.
UPDATE 1 1 1 23. updates the cell (1,1,1) to 23. QUERY 2 2 2 4 4 4. Only the cell (1,1,1) and (2,2,2) are non-zero and (1,1,1) is not between (2,2,2) and (4,4,4). So, the answer is 4.
QUERY 1 1 1 3 3 3. 2 cells are non-zero and their sum is 23+4 = 27.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
typedef struct s_elem
{
int x;
int y;
int z;
long long int value;
struct s_elem *next;
} elem;
int place_value(elem *root, int x, int y, int z, long long int value)
{
while (root != NULL)
{
if (root -> x == x && root -> y == y && root -> z == z)
{
root->value = value;
return 1;
}
root = root->next;
}
return 0;
}
void add_elem(elem **root, int x, int y, int z, long long int value)
{
elem *newelem = (elem *) malloc(sizeof(elem));
newelem->x = x;
newelem->y = y;
newelem->z = z;
newelem->value = value;
newelem->next = *root;
*root = newelem;
}
long long int sum_list(elem *root, int x1, int y1, int z1, int x2, int y2, int z2)
{
long long int sum = 0;
while (root != NULL)
{
if (root->x >= x1 && root->x < = x2 && root->y >= y1 && root->y <= y2 && root->z >= z1 && root->z <= z2)
sum += root->value;
root = root->next;
}
return sum;
}
void free_list(elem **root)
{
elem *tmp, *current = *root;
while (current != NULL)
{
tmp = current->next;
free(current);
current = tmp;
}
*root = NULL;
}
int main()
{
int test, i, j, size, query;
int x, y, z, x1, y1, z1, x2, y2, z2;
long long int value;
elem *list = NULL;
char *str = malloc(sizeof(char) * 10);
scanf("%d", &test);
for (i = 0; i < test; i++)
{
scanf("%d%d", &size, &query);
for (j = 0; j < query; j++)
{
scanf("%s", str);
if (str[0] == 'U')
{
scanf("%d%d%d%lld", &x, &y, &z, &value);
if (!place_value(list, x, y, z, value))
{
add_elem(&list, x, y, z, value);
}
}
else
{
scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);
printf("%lld\n", sum_list(list, x1, y1, z1, x2, y2, z2));
}
}
free_list(&list);
}
return 0;
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <fstream>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 110;
int T, N, M, X1, Y1, Z1, X2, Y2, Z2, Val[NMAX][NMAX][NMAX];
long long Aib[NMAX][NMAX][NMAX];
char Type[20];
int LSB(int X)
{
return (X & (X - 1)) ^ X;
}
void Update(int X, int Y, int Z, int Val)
{
for(int i = Y; i < = N; i += LSB(i))
for(int j = Z; j < = N; j += LSB(j))
Aib[X][i][j] += Val;
}
long long Query(int X, int Y, int Z)
{
long long Now = 0;
for(int i = Y; i; i -= LSB(i))
for(int j = Z; j; j -= LSB(j))
Now += Aib[X][i][j];
return Now;
}
long long Sum(int X1, int Y1, int Z1, int X2, int Y2, int Z2)
{
long long Ans = 0;
for(int i = X1; i < = X2; ++ i)
Ans += (Query(i, Y2, Z2) - Query(i, Y1 - 1, Z2) - Query(i, Y2, Z1 - 1) + Query(i, Y1 - 1, Z1 - 1));
return Ans;
}
int main()
{
cin >> T;
for(; T; T --)
{
for(int i = 1; i < = N; ++ i)
for(int j = 1; j < = N; ++ j)
for(int k = 1; k < = N; ++ k)
Aib[i][j][k] = Val[i][j][k] = 0;
cin >> N >> M;
for(int i = 1; i < = M; ++ i)
{
cin >> Type;
if(Type[0] == 'U')
{
int W;
cin >> X1 >> Y1 >> Z1 >> W;
Update(X1, Y1, Z1, -Val[X1][Y1][Z1]);
Update(X1, Y1, Z1, W);
Val[X1][Y1][Z1] = W;
}else
{
cin >> X1 >> Y1 >> Z1 >> X2 >> Y2 >> Z2;
cout << Sum(X1, Y1, Z1, X2, Y2, Z2) << "\n";
}
}
}
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.*;
import java.util.*;
public class Solution {
public static void update(int[][][]cube, int x,int y, int z, int W) {
cube[x-1][y-1][z-1] = W;
}
public static long query(int[][][] cube, int x1, int y1, int z1, int x2, int y2, int z2) {
long total = 0L;
if (x1>x2) {
int temp = x1;
x1 = x2;
x2 = temp;
}
if (y1>y2) {
int temp = y1;
y1 = y2;
y2 = temp;
}
if (z1>z2) {
int temp = z1;
z1 = z2;
z2 = temp;
}
for (int i = x1; i < = x2; i++) {
for (int j = y1; j < = y2; j++) {
for (int k = z1; k < = z2; k++) {
long temp = (long)cube[i-1][j-1][k-1];
total+=temp;
}
}
}
return total;
}
public static void main(String[] args) {
Scanner inp = new Scanner(System.in);
int T = inp.nextInt();
for (int i = 0; i < T; i++) {
int N = inp.nextInt();
int M = inp.nextInt();
int [][][] cube = new int [N][N][N];
for (int j = 0; j < M; j++) {
String op = inp.next();
if (op.equals("UPDATE")) {
update(cube,inp.nextInt(),inp.nextInt(),inp.nextInt(),inp.nextInt());
} else {
System.out.println(query(cube,inp.nextInt(),inp.nextInt(),inp.nextInt(),inp.nextInt(),inp.nextInt(),inp.nextInt()));
}
}
}
}
}
#5 Code Example with Javascript Programming
Code -
Javascript Programming
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', function(inputStdin) {
inputString += inputStdin;
});
process.stdin.on('end', function() {
inputString = inputString.split('\n');
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the 'cubeSum' function below.
*
* The function is expected to return an INTEGER_ARRAY.
* The function accepts following parameters:
* 1. INTEGER n
* 2. STRING_ARRAY operations
*/
function cubeSum(n, operations) {
// Write your code here
// sparse matrix? + hash + bloomFilter
let i = -1;
const map = new Map();
const queries = [];
while (++i < operations.length) {
const op = operations[i].split(' ');
const name = op[0];
switch (name) {
case 'UPDATE':
const [_u, x, y, z, w] = op.map(a => +a);
const key = `${x}_${y}_${z}`;
map.set(key, w);
break;
case 'QUERY':
const [_q, x1, y1, z1, x2, y2, z2] = op.map(a => +a);
let sum = 0
for (const pair of map) {
const [key, value] = pair;
const [x,y,z] = key.split('_').map(a => +a);
if (
x >= x1 && x < = x2 &&
y >= y1 && y <= y2 &&
z >= z1 && z <= z2
) {
sum += value;
}
}
queries.push(sum);
break;
default:
return;
}
}
return queries;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const T = parseInt(readLine().trim(), 10);
for (let TItr = 0; TItr < T; TItr++) {
const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');
const matSize = parseInt(firstMultipleInput[0], 10);
const m = parseInt(firstMultipleInput[1], 10);
let ops = [];
for (let i = 0; i < m; i++) {
const opsItem = readLine();
ops.push(opsItem);
}
const res = cubeSum(matSize, ops);
ws.write(res.join('\n') + '\n');
}
ws.end();
}
#5 Code Example with Python Programming
Code -
Python Programming
import os
import sys
def cubeSum(cmds):
cube={}
for i in cmds:
if(i[0]=="UPDATE"):
x=cube.get(i[1], dict())
y=x.get(i[2], dict())
y[i[3]]=i[4]
x[i[2]]=y
cube[i[1]]=x
else:
sums=0
for j in cube:
if(j>=i[1] and j<=i[4]>:
for k in cube[j]:
if(k>=i[2] and k<=i[5]>:
for l in cube[j][k]:
if(l>=i[3] and l<=i[6]):
sums+=cube[j][k][l]
print(sums)
if __name__ == '__main__':
tests=int(input())
for i in range(tests):
[N, M]=[int(var) for var in input().split()]
cmds=[]
for j in range(M):
ip=input().split()
for k in range(1, len(ip)):
ip[k]=int(ip[k])
cmds.append(ip)
cubeSum(cmds>