In this HackerRank Counting Special Sub-Cubes problem solution, we have given an n x n x n cube. let f(x,y,z) denote the value stored in the cell. and we also have given k x k x k subcube of an n x n x n cube that is considered to be special if the maximum value stored in any cell in the subcube is equal to k. so for each k in the inclusive range [1,n] we need to calculate the number of special sub cubes. then print the count as a single line space-separated integers.
Problem solution in Python.
#!/bin/python3
import os
import sys
#
# Complete the specialSubCubes function below.
#
def specialSubCubes(n, cube):
#
# Write your code here.
#
res = []
n2 = n * n
for k in range(1, n + 1):
res.append(0)
for x in range(n - k + 1):
for y in range(n - k + 1):
for z in range(n - k + 1):
i = x * n2 + y * n + z
if k == 1:
if cube[i] == 1:
res[-1] += 1
else:
cube[i] = max(cube[i], cube[i + 1], cube[i + n], cube[i + 1 + n], cube[i + n2], cube[i + 1 + n2], cube[i + n + n2], cube[i + 1 + n + n2])
if cube[i] == k:
res[-1] += 1
return res
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
q = int(input())
for q_itr in range(q):
n = int(input())
cube = list(map(int, input().rstrip().split()))
result = specialSubCubes(n, cube)
fptr.write(' '.join(map(str, result)))
fptr.write('\n')
fptr.close()
Problem solution in Java.
import java.util.Scanner;
class Solution{
static byte[][][] deepCopy(byte[][][] grid){
int n=grid.length;
byte[][][] out=new byte[n][n][n];
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
for(int k=0;k<n;++k){
out[i][j][k]=grid[i][j][k];
}
}
}
return out;
}
static int countOnes(byte[][][] grid){
int n=grid.length, ones=0;
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
for(int k=0;k<n;++k){
if(1==grid[i][j][k]) ++ones;
}
}
}
return ones;
}
static byte larger(byte a, byte b){ return a>b?a:b; }
static int[] solve(byte[][][] grid){
int n=grid.length, sp[]=new int[n];
byte[][][] max=deepCopy(grid);
byte[][][] next=new byte[n][n][n];
sp[0]=countOnes(max);
for(int l=1;l<n;++l){
int count=0;
for(int i=0;i<n-l;++i){
for(int j=0;j<n-l;++j){
for(int k=0;k<n-l;++k){
byte best=0;
for(int q=0;q<8;++q){
int di=q>>0&1;
int dj=q>>1&1;
int dk=q>>2&1;
byte m=max[i+di][j+dj][k+dk];
best=larger(best,m);
}
next[i][j][k]=best;
if(best==l+1) ++count;
}
}
}
sp[l]=count;
byte[][][] temp=max;
max=next;
next=temp;
}
return sp;
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int q=sc.nextInt();
while(q-- != 0){
int n=sc.nextInt();
byte[][][] grid=new byte[n][n][n];
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
for(int k=0;k<n;++k){
grid[i][j][k]=sc.nextByte();
}
}
}
int[] res=solve(grid);
StringBuilder sb=new StringBuilder();
for(int x: res) sb.append(x+" ");
System.out.println(sb);
}
sc.close();
}
}
Problem solution in C++.
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN = 50;
int main() {
int T, n;
int c[2][MAXN][MAXN][MAXN];
cin >> T;
while (T--) {
cin >> n;
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
for (int z = 0; z < n; z++) {
cin >> c[0][x][y][z];
}
}
}
for (int k = 1; k <= n; k++) {
int s = 0, k0 = 1-(k&1), k1 = k&1;
for (int x = 0; x <= n-k; x++) {
for (int y = 0; y <= n-k; y++) {
for (int z = 0; z <= n-k; z++) {
s += c[k0][x][y][z] == k;
if (x < n-k && y < n-k && z < n-k) {
c[k1][x][y][z] = c[k0][x][y][z];
for (int d = 0; d < 8; d++) {
c[k1][x][y][z] = max(c[k1][x][y][z], c[k0][x+(d>>2)][y+((d>>1)&1)][z+(d&1)]);
}
}
}
}
}
cout << s << " ";
}
cout << endl;
}
return 0;
}
Problem solution in C.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int q;
scanf("%d", &q);
while (q--) {
int n, f;
scanf("%d", &n);
char cube[n][n][n][n]; // hope there is enough stack space for this...
int count[n];
for (int i = 0; i < n; i++) count[i] = 0;
for (int z = 0; z < n; z++) {
for (int y = 0; y < n; y++) {
for (int x = 0; x < n; x++) {
scanf("%d", &f);
cube[x][y][z][0] = f;
if (f == 1) count[0]++;
}
}
}
for (int k = 1; k < n; k++) {
// k + 1 == cubesize
if (k % 2 == 0) { // cubesize is odd
for (int z = k; z < n; z++) {
for (int y = k; y < n; y++) {
for (int x = k; x < n; x++) {
int m = cube[x][y][z][k-1];
if (cube[x-1][y][z][k-1] > m) m = cube[x-1][y][z][k-1];
if (cube[x][y-1][z][k-1] > m) m = cube[x][y-1][z][k-1];
if (cube[x][y][z-1][k-1] > m) m = cube[x][y][z-1][k-1];
if (cube[x-1][y-1][z][k-1] > m) m = cube[x-1][y-1][z][k-1];
if (cube[x-1][y][z-1][k-1] > m) m = cube[x-1][y][z-1][k-1];
if (cube[x][y-1][z-1][k-1] > m) m = cube[x][y-1][z-1][k-1];
if (cube[x-1][y-1][z-1][k-1] > m) m = cube[x-1][y-1][z-1][k-1];
cube[x][y][z][k] = m;
if (m == k+1) count[k]++;
}
}
}
} else { // cubesize is even
for (int z = k; z < n; z++) {
for (int y = k; y < n; y++) {
for (int x = k; x < n; x++) {
int h = k / 2, d = (k + 1) / 2;
int m = cube[x][y][z][h];
if (cube[x][y-d][z][h] > m) m = cube[x][y-d][z][h];
if (cube[x][y][z-d][h] > m) m = cube[x][y][z-d][h];
if (cube[x][y-d][z-d][h] > m) m = cube[x][y-d][z-d][h];
if (cube[x-d][y][z][h] > m) m = cube[x-d][y][z][h];
if (cube[x-d][y-d][z][h] > m) m = cube[x-d][y-d][z][h];
if (cube[x-d][y][z-d][h] > m) m = cube[x-d][y][z-d][h];
if (cube[x-d][y-d][z-d][h] > m) m = cube[x-d][y-d][z-d][h];
cube[x][y][z][k] = m;
if (m == k+1) count[k]++;
}
}
}
}
}
for (int k = 0; k < n; k++) {
printf("%d ", count[k]);
}
printf("\n");
}
return 0;
}
0 Comments