You are not logged in. Please login at www.codechef.com to post your questions!

×

CHFBINS - Editorial

PROBLEM LINK:

Practice

Contest

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.

This question is marked "community wiki".

asked 08 Oct, 19:59

rahul_ojha_07's gravatar image

3★rahul_ojha_07
12
accept rate: 0%

edited 11 Oct, 17:17

admin's gravatar image

0★admin ♦♦
19.5k348496535

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×162

question asked: 08 Oct, 19:59

question was seen: 43 times

last updated: 11 Oct, 17:17