HackerEarth Binary Blocks problem solution

In this HackerEarth Binary Blocks problem solution, You are given an image, that can be represented with a 2-d n by m grid of pixels. Each pixel of the image is either on or off, denoted by the character ‘0’ or ‘1’, respectively.

You would like to compress this image. You want to choose an integer k > 1 and split the image into k by k blocks. If n and m are not divisible by k, the image to be padded with 0’s to the right and/or to the bottom. Each pixel in each individual block must have the same value.

The given image may not be compressible in its current state. Find the minimum number of pixels you need to toggle(padded pixels also can be toggled) in order for the image to be compressible for some k.

More specifically, the steps are to first choose k, then the image is padded with 0s, then, we can toggle the pixels so it is compressible for some k. The image must be compressible in that state.

HackerEarth Binary Blocks problem solution.

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        BinaryBlocks solver = new BinaryBlocks();
        solver.solve(1, in, out);
        out.close();
    }

    static class BinaryBlocks {
        public int[][] grid;

        public int sum(int x1, int y1, int x2, int y2) {
            x2 = Math.min(grid.length - 1, x2);
            y2 = Math.min(grid[0].length - 1, y2);

            return grid[x2][y2] - grid[x2][y1 - 1] - grid[x1 - 1][y2] + grid[x1 - 1][y1 - 1];
        }

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt(), m = in.nextInt();
            grid = new int[n + 1][m + 1];
            for (int i = 1; i <= n; i++) {
                char[] c = in.next().toCharArray();
                for (int j = 1; j <= m; j++) {
                    grid[i][j] = c[j - 1] - '0' + grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1];
                }
            }

            int ret = n * m;
            for (int k = 2; k < Math.max(n, m); k++) {
                int ss = 0;
                for (int x = 1; x <= n; x += k) {
                    for (int y = 1; y <= m; y += k) {
                        int g = sum(x, y, x + k - 1, y + k - 1);
                        ss += Math.min(g, k * k - g);
                    }
                }
                ret = Math.min(ret, ss);
            }
            out.println(ret);
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void println(int i) {
            writer.println(i);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public String next() {
            int c;
            while (isSpaceChar(c = this.read())) {
                ;
            }

            StringBuilder result = new StringBuilder();
            result.appendCodePoint(c);

            while (!isSpaceChar(c = this.read())) {
                result.appendCodePoint(c);
            }

            return result.toString();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }
}

coding problems solutions