HackerRank Counting Special Sub-Cubes
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:
- The first line contains an integer, n, denoting the side length of the initial cube.
- 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 1Explanation
We must perform the following q = 2 queries:
- 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), - 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).
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('')
