[Solved]: Minimal DFA that accepts binary strings whose decimal equivalent is divisible by 32

Problem Detail: 

I thought the answer would be 32 for remainder $0,1,2,\dots, 31$. But answer given as $6$. and explanation is given as if the number is $2^n$ then number of states required would be $n+1$.

Asked By : Vikrant

Answered By : David Richerby

The idea of using remainders is perfect for the general problem of "Recognize base-$b$ strings representing a number divisible by $k$" for some general, fixed $b$ and $k$. However, it's not optimal for certain combinations of $b$ and $k$ where you can tell that the number is divisible by $k$ "just by looking at it." For example, if I asked you to recognize decimal numbers divisible by $100\,000$, you wouldn't be messing around with remainders: you'd use a nice textual property of decimal numbers divisible by powers of ten.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37949