Q$5.(30$ pts$)$ Consider a bit$-$string of length $n.$ Your goal is to find the number of substrings that do not include $1.$ For example, if the input is $001000,$ the answer would be $9($five $0,$ three $00,$ one $000).$

$($a $-20$ pts$)$ Describe a Divide and Conquer algorithm. Give the worst case time complexity of your algorithm.

$($b$-10$ pts$)$ Describe another algorithm that is at least as good as $($or better than$)$ Divide and Conquer algorithm. Give its time complexity as well.

Do not give pseudocode! Step$-$by$-$step description please.