PROBLEM LINK:
Author: rahul_ojha_07
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Binary numbers
PROBLEM:
Given a Binary String, we need to count the number of odd decimal equivalent which can be possibly made by the right shift of the digits of the string.
QUICK EXPLANATION:
To be simple just count the number of 1’s in the string and print.
EXPLANATION:
At first glance, this problem may sound hard. You can’t generate each string and check it straightforwardly in O(n 2) - that’s too slow. However, there is only one important observation needed: you are asked to count shifts with fixed remainder modulo 2, and the string itself is binary. When considering digits of binary number starting from the rightmost, first digits is X x 20, second is X x 20, third is X x 20 and so on - all addends except of very first are divisible by 2 for sure, Therefore remainder depends on last digit only. Just like we can figure out remainder after division by 10 for the number in base10 by simply looking at its last digit, in this problem we can say that number is odd if and only if its last bit is 1. It means that answer to the problem is equal to the number of shifts ending with 1, and that number is equal to count of 1’s in given string. You may even not store the whole string, but read it char by char and update answer after reading each digit.
Author’s solution can be found here.