StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POAlgorithm to calculate the number of 1s for a range of numbers in binary
text
Body
copied!<p>So I just got back for the <strong>ACM Programing competition</strong> and did pretty well but there was one problem that not one team got.</p> <p>The Problem.</p> <blockquote> <p>Start with an integer N0 which is greater than 0. Let N1 be the number of ones in the binary representation of N0. So, if <code>N0 = 27</code>, <code>N1 = 4</code>. For all <code>i > 0</code>, let Ni be the number of ones in the binary representation of <code>Ni-1</code>. This sequence will always converge to one. For any starting number, N0, let K be the minimum value of i >= 0 for which N1 = 1. For example, if N0 = 31, then N1 = 5, N2 = 2, N3 = 1, so K = 3.</p> <p>Given a range of consecutive numbers and a value of X how many numbers in the range have a K value equal to X?</p> <p><strong>Input</strong><br> There will be several test cases in the input. Each test case will consist of three integers on a single line: <code>LO HI X</code><br> Where <code>LO</code> and <code>HI</code> (1 <= <code>LO</code> <= <code>HI</code> <= 10^18) are the lower and upper limits of a range of integers, and <code>X</code> (0 <= <code>X</code> <= 10) is the target value for K. The input will end with a line of three 0s.</p> <p><strong>Output</strong><br> For each test case output a single integer, representing the number of integers in the range from <code>LO</code> to <code>HI</code> (inclusive) which have a K value equal to X in the input. Print each Integer on its own line with no spaces. Do not print any blank lines between answers.</p> </blockquote> <h3>Sample Input</h3> <pre><code>31 31 3 31 31 1 27 31 1 27 31 2 1023 1025 1 1023 1025 2 0 0 0 </code></pre> <h3>Sample Output</h3> <pre><code>1 0 0 3 1 1 </code></pre> <hr> <p>If you guys want I can include our answer or our problem, because finding for a small range is easy but I will give you a hint first your program needs to run in <em>seconds</em> not minutes. We had a successful solution but not an efficient algorithm to use a range similar to </p> <pre><code>48238 10^18 9 </code></pre> <p>Anyway good luck and if the community likes these we had some more we could not solve that could be some good brain teasers for you guys. The competition allows you to use Python, C++, or Java—all three are acceptable in an answer.</p> <hr> <p>So as a hint my coach said to think of how binary numbers count rather than checking every bit. I think that gets us a lot closer.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload