HackerRank Counting Special Sub-Cubes

Yashwant Parihar,

In this post, we will solve HackerRank Counting Special Sub-Cubes Problem Solution.

Given an n x n x n cube, let f(x, y, z) (where 1 < x, y, z <n) denote the value stored in cell (x, y, z).
Akxkx k sub-cube (where 1 < k < n) of an n xnxn cube is considered to be special if the maximum value stored in any cell in the sub-cube is equal to k. For each k in the inclusive range [1, 2], calculate the number of special sub-cubes. Then print each count as a single line of space-separated integers (l.e.. count count2… count).
Input Format
The first line contains an integer, q, denoting the number of queries. The 2. q subsequent lines describe each query over two lines:

  1. The first line contains an integer, n, denoting the side length of the initial cube.
  2. The second line contains n³ space-separated integers describing an array of n³ integers in the form a0, a1, a³-1 The integer in some cell (x, y, z) is calculated using the formula a[(x-1). n²+(y-1) . n + 2].

Output Format

For each query, print n space-separated integers where the ith integer denotes the number of special sub-cubes for k= i.

Sample Input

2
2
2 1 1 1 1 1 1 1
2
1 1 1 1 2 1 1 2

Sample Output

7 1
6 1

Explanation
We must perform the following q = 2 queries:

  1. We have a cube of size n = 2 and must calculate the number of special sub-cubes for the following values of k:
    k = 1: There are 23 = 8 sub-cubes of size 1 and seven of them have a maximum value of 1 written inside them. So, for k = 1, the answer is 7.
    k = 2: There is only one sub-cube of size 2 and the maximum number written inside it is 2. So, for k = 2, the answer is 1.
    We then print the respective values for each k as a single line of space-separated
    integers (i.e., 7. 1),
  2. We have a cube of size n = 2 and must calculate the number of special sub-cubes for the following values of k:
    k = 1: There are 23 = 8 sub-cubes of size 1 and six of them have a maximum value of 1 written inside them. So, for k = 1, the answer is 6.
    k = 2: There is only one sub-cube of size 2 and the maximum number written inside it is 2. So, for k = 2, the answer is 1.
    We then print the respective values for each k as a single line of space-separated integers (l.e., 6 1).
HackerRank Counting Special Sub-Cubes Problem Solution
HackerRank Counting Special Sub-Cubes Problem Solution

Counting Special Sub-Cubes C Solution

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

Counting Special Sub-Cubes C++ Solution

#include <iostream>
#include <vector>

using namespace std;

#define vvi vector<vector<int> >
#define vvvi vector<vvi>
#define vvvvi vector<vvvi>
#define rel fourd[k][x][y][z]

int max_4(int a = 0, int b = 0, int c =0, int d = 0) {
	if (a>=b && a>=c && a>=d) return a;
	if (b>=c && b>=d) return b;
	if (c>=d) return c;
	return d;
}

int min_4(int a = 0, int b = 0, int c =0, int d = 0) {
	if (a<=b && a<=c && a<=d) return a;
	if (b<=c && b<=d) return b;
	if (c<=d) return c;
	return d;
}

int main() { 
	vector<int> oned(51, -1);
	vvi twod(51, oned);
	vvvi threed( 51, twod);
	vvvvi fourd(51, threed);

	int t;
	int konst = 50*50*50+5;
	vector<int> arr(konst);
	int num;
	cin>>t;
	while(t--) {
		cin>>num;
		vector<int> result(num+1, 0);
		for(int i=1; i<=num*num*num; i++) {
			cin>>arr[i];
		}
		for(int k = 1; k<=num; k++){
			for(int x=1; x<=num; x++) {
				for(int y=1; y<=num; y++) {
					for(int z=1; z<=num; z++) {
						int coeff = (x - 1)*num*num + (y - 1)*num + z;
						threed[x][y][z] = arr[coeff];
						if(k==1) {
							fourd[k][x][y][z] = threed[x][y][z];
							if (fourd[k][x][y][z] == k) result[k]+=1;
							continue;
						}
						if(min_4(x, y, z, k) != k) {
							fourd[k][x][y][z] = 0;					
							continue;
						}
						int temp = max_4(fourd[k-1][x-1][y][z], fourd[k-1][x][y-1][z], fourd[k-1][x][y][z-1]);
						temp = max_4(fourd[k-1][x-1][y-1][z], fourd[k-1][x][y-1][z-1], fourd[k-1][x-1][y][z-1], temp);
						temp = max_4(temp, fourd[k-1][x-1][y-1][z-1], threed[x][y][z]);
						fourd[k][x][y][z] = temp;
						if(temp == k) {
							result[k]+=1;	
						}
					}
				}
			}	
		}
		for(int i=1; i<= num; i++) {
			cout<<result[i]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

Counting Special Sub-Cubes C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        var iterations = int.Parse(Console.ReadLine());
        for (var i = 0; i < iterations; i++) 
        {
            var size = int.Parse(Console.ReadLine());
            var values = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            var answer = Calculate(size, values);
            
            Console.WriteLine(string.Join(" ", answer));
        }
    }
    
    //invalid = if a sub cube were to start at this place, it will contain a value that is higher than k
        //OutOfBound = this cell cannot be the start of the cube because it cannot contain its size
        //valid = place that will contain a cube if started from here 
        enum CellStatus { Invalid, OutOfBound, Valid, NotExplored }
        public static int[] Calculate(int n, int[] cells)
        {
            //first, construct a 3d cube
            var valueCube = new int[n, n, n];

            var answer = new List<int>();

            var count = 0;
            for (var i = 0; i < n; i++)
            {
                for (var j = 0; j < n; j++)
                {
                    for (var k = 0; k < n; k++)
                    {
                        valueCube[i, j, k] = cells[count];
                        count++;
                    }
                }
            }

            answer.Add(CountOnes(cells));

            for (var val = 2; val < n; val++)
            {
                var statusCube = GetInitCell(val, n);

                //first valid possible cells
                for (var i = 0; i < n; i++)
                {
                    for (var j = 0; j < n; j++)
                    {
                        for (var k = 0; k < n; k++)
                        {
                            if (valueCube[i, j, k] == val)
                            {
                                ValidCell(statusCube, i, j, k, val);
                            }
                        }
                    }
                }

                //then invalid cells
                for (var i = 0; i < n; i++)
                {
                    for (var j = 0; j < n; j++)
                    {
                        for (var k = 0; k < n; k++)
                        {
                            if (valueCube[i, j, k] > val)
                            {
                                InvalidCell(statusCube, i, j, k, val);
                            }
                        }
                    }
                }

                //finally count it
                var validCount = CountValids(statusCube, n);

                answer.Add(validCount);
            }
            
            if (n > 1)
            {
                answer.Add(CountMax(cells, n));
            }

            return answer.ToArray();
        }

        private static int CountValids(CellStatus[,,] cube, int n)
        {
            var valids = 0;
            for (var i = 0; i < n; i++)
            {
                for (var j = 0; j < n; j++)
                {
                    for (var k = 0; k < n; k++)
                    {
                        if (cube[i, j, k] == CellStatus.Valid)
                        {
                            valids++;
                        }
                    }
                }
            }
            return valids;
        }

        private static void ValidCell(CellStatus[,,] cube, int x, int y, int z, int val)
        {
            AdjustCell(cube, x, y, z, val, CellStatus.Valid);
        }

        private static void InvalidCell(CellStatus[,,] cube, int x, int y, int z, int val)
        {
            AdjustCell(cube, x, y, z, val, CellStatus.Invalid);
        }

        private static void AdjustCell(CellStatus[,,] cube, int x, int y, int z, int val, CellStatus status)
        {
            for (var i = 0; i < val; i++)
            {
                for (var j = 0; j < val; j++)
                {
                    for (var k = 0; k < val; k++)
                    {
                        if (x - i < 0 || y - j < 0 || z - k < 0)
                        {
                            continue;
                        }
                        if (cube[x - i, y - j, z - k] != CellStatus.OutOfBound)
                        {
                            cube[x - i, y - j, z - k] = status;
                        }
                    }
                }
            }
        }

        private static CellStatus[,,] GetInitCell(int val, int n)
        {
            var bound = n - val;
            var toReturn = new CellStatus[n, n, n];
            for (var i = 0; i < n; i++)
            {
                for (var j = 0; j < n; j++)
                {
                    for (var k = 0; k < n; k++)
                    {
                        if (i > bound || j > bound || k > bound)
                        {
                            toReturn[i, j, k] = CellStatus.OutOfBound;
                        }
                        else
                        {
                            toReturn[i, j, k] = CellStatus.NotExplored;
                        }
                    }
                }
            }

            return toReturn;
        }

        private static int CountOnes(int[] cells)
        {
            //special case for counting ones... literally just count how many 1s are ther
            return cells.Where(s => s == 1).Count();
        }

        private static int CountMax(int[] cells, int max)
        {
            return cells.Any(s => s == max) ? 1 : 0;
        }
    
}

Counting Special Sub-Cubes Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'specialSubCubes' function below.
     *
     * The function is expected to return an INTEGER_ARRAY.
     * The function accepts INTEGER_ARRAY cube as parameter.
     */

    public static List<Integer> specialSubCubes(int n, List<Integer> cube) {
        int[][][] a = new int[n+1][n+1][n+1];
        
        {
            int k = 0;
            for (int x=1; x<=n; x++){
                for (int y=1; y<=n; y++){
                    for (int z=1; z<=n; z++){
                        a[x][y][z] = cube.get(k);
                        k++;
                    }
                }
            }
        }
        
        int[][][][] m = new int[n+1][n+1][n+1][n+1];
        for (int x=1; x<=n; x++){
            for (int y=1; y<=n; y++){
                for (int z=1; z<=n; z++){
                    for (int k=1; k<=n; k++){
                        if (x<k || y<k || z<k){
                            m[x][y][z][k] = 0;
                        } else {
                            m[x][y][z][k] = 
                                IntStream.of(
                                    a[x][y][z],
                                    m[x-1][y-1][z-1][k-1],
                                    m[x-1][y-1][z][k-1],
                                    m[x-1][y][z-1][k-1],
                                    m[x][y-1][z-1][k-1],
                                    m[x][y-1][z][k-1],
                                    m[x][y][z-1][k-1],
                                    m[x-1][y][z][k-1])
                                    .max().orElse(0);
                        }
                    }
                }
            }
        }
        int[] results = new int[n+1];
        for (int x=1; x<=n; x++){
            for (int y=1; y<=n; y++){
                for (int z=1; z<=n; z++){
                    for (int k=1; k<=n; k++){
                        if (m[x][y][z][k]==k){
                            results[k]++;
                        }
                    }
                }
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int k=1; k<=n; k++){
            result.add(results[k]);
        }
        return result;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, q).forEach(qItr -> {
            try {
                int n = Integer.parseInt(bufferedReader.readLine().trim());

                List<Integer> cube = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                    .map(Integer::parseInt)
                    .collect(toList());

                List<Integer> result = Result.specialSubCubes(n, cube);

                bufferedWriter.write(
                    result.stream()
                        .map(Object::toString)
                        .collect(joining(" "))
                    + "\n"
                );
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Counting Special Sub-Cubes JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the specialSubCubes function below.
 */
function specialSubCubes(n, cube) {
    /*
     * Write your code here.
     */
    //console.log(n, cube);
    function idx(sz, i, j, k) {
        return k + n * j + n * n * i + n * n * n * (sz - 1);
    }
    let smax = [];
    let total = [];
    let coords = [
        [1, 0, 0],
        [0, 1, 0],
        [1, 1, 0],
        [0, 0, 1],
        [1, 0, 1],
        [0, 1, 1],
        [1, 1, 1],
    ];
    for (let sz = 1; sz <= n; ++sz) {
        total.push(0);
        for (let i = 0; i < n; ++i) {
            for (let j = 0; j < n; ++j) {
                for (let k = 0; k < n; ++k) {
                    if (sz == 1) {
                        smax.push(cube[idx(sz, i , j, k)]);
                        if (cube[idx(sz, i, j, k)] == sz) {
                            total[sz - 1]++;
                        }
                    } else {
                        smax.push(-1);
                    }
                }
            }
        }
    }
    for (let sz = 2; sz <= n; ++sz) {
        for (let i = 0; i < n; ++i) {
            for (let j = 0; j < n; ++j) {
                for (let k = 0; k < n; ++k) {
                    let best = smax[idx(sz - 1, i, j, k)];
                    //console.log("smax", smax, "idx", idx(sz - 1, i, j, k));
                    for (let c = 0; c < coords.length; ++c) {
                        let [c1, c2, c3] = coords[c];
                        if (i + c1 < n && j + c2 < n && k + c3 < n) {
                            best = Math.max(best,
                                smax[idx(sz - 1, i + c1, j + c2, k + c3)]
                            );
                        }
                    }
                    //console.log(sz, i, j, k, " = ", best);
                    smax[idx(sz, i, j, k)] = best;
                    if (i + sz > n || j + sz > n || k + sz > n) {
                        continue;
                    }
                    if (best == sz) {
                        total[sz - 1]++;
                    }
                }
            }
        }
    }
    return total;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const q = parseInt(readLine(), 10);

    for (let qItr = 0; qItr < q; qItr++) {
        const n = parseInt(readLine(), 10);

        const cube = readLine().split(' ').map(cubeTemp => parseInt(cubeTemp, 10));

        let result = specialSubCubes(n, cube);

        ws.write(result.join(" ") + "\n");
    }

    ws.end();
}

Counting Special Sub-Cubes Python Solution


def findMax(arr, s, indices, n):
    largest = 1
    for i in indices:
        cur = arr[s+i]
        if cur > largest:
            largest = cur
        elif cur == n:
            largest = n
            break
    return largest

def findSpecial(arr, k, n):
    temp = arr
    if k > 1:
        temp = []
        m = n - k + 2
        m2 = m*m
        indices = [0, 1, m, m+1, m2, m2+1, m2+m, m2+m+1]
        for i in range(m-1):
            start = m2*i
            for j in range(m-1):
                for z in range(m-1):
                    largest = findMax(arr, start, indices, n)
                    temp.append(largest)
                    start += 1
                start += 1
    return temp    
               
q = int(input())
for _ in range(q):
    n = int(input())
    arr = list(map(int, input().split()))
    for k in range(1, n+1):
        arr = findSpecial(arr, k, n)
        print(arr.count(k), end=' ')
    print('')
c C# C++ HackerRank Solutions java javascript python