All Tracks Data Structures Arrays Multi-dimensional Problem

Binary Blocks
Tag(s):

Data Structures, Easy

Problem
Editorial
Analytics

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.

Input Format

The first line of input will contain two integers \(n,m\), the dimensions of the image.

The next n lines of input will contain a binary string with exactly m characters, representing the image.

Output Format

Print a single integer, the minimum number of pixels needed to toggle to make the image compressible.

Constraints

\(2 \leq n,m \leq 2\,500\)

SAMPLE INPUT
3 5
00100
10110
11001
SAMPLE OUTPUT
5
Explanation

We first choose \(k=2\).

The image is padded as follows:

001000
101100
110010
000000

We can toggle the image to look as follows:

001100
001100
000000
000000

We can see that this image is compressible for \(k = 2\).

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

IndiaHacks 2017: Programming [Wave 2.0- Eliminator]

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?