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.

hackerrank counting special sub cubes problem solution


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()

{"mode":"full","isActive":false}


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();
    }
}

{"mode":"full","isActive":false}


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;
}

{"mode":"full","isActive":false}


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;
}

{"mode":"full","isActive":false}