CODEWITHSUNDEEP
pythonalgorithm
Mayukh Sarkar
Mayukh Sarkar

Reputation: 2625

Why I am getting a one less count always

I am solving a problem in Codeforce and this was my previous submission

#!/usr/local/bin/python

limit = 10**18
string = raw_input()
year1, year2 = string.split()
year1 = int(year1)
year2 = int(year2)
x = 1
count = 0
a = []
while True:
    k = 2**x - 1

    if k > limit:
        break
    else:
        for i in xrange(len(bin(k)[2:])):
            if year1 <= k - (1 << i) <= year2 and len(bin(k - (1 << i))[2:].split('0')) == 2:
                count += 1
    x += 1
print count

It worked for all the given values but it gave one less count value for the range 1 to 1000000000000000000. It was hard to debug and hence I put a hacked up code before the last print like this

if year2 - year1 + 1 == limit:
    count += 1

and it worked for that value but again gave one less value value for another range, 1 to 935829385028502935.

No wonder that the logic-less hack didn't work but I want to know that why it gave one less count value previously ?

Upvotes: 0

Views: 127

Answers (2)

dejvuth
dejvuth

Reputation: 7146

You need to increase limit by another order of magnitude:

limit = 10**19

Otherwise you'd miss 864691128455135231, obtained from 1152921504606846975 - (1 << 58).

(Observe that 1152921504606846975 > 10**18.)

Upvotes: 3

SashaMN
SashaMN

Reputation: 708

I tried to simplify code (it works now, Accepted):

limit = 10**19 # this change is important because otherwise you will loose 1 solution
# k > limit and exists such i that k - (1 << i) < limit

string = raw_input()
year1, year2 = string.split()
year1 = int(year1)
year2 = int(year2)
x = 1
count = 0
a = []
while True:
    k = 2**x - 1
    if k > limit:
        break

    for i in xrange(x - 1): # k has exactly x bits. So we have only x-1 chances to set zero bit
        if year1 <= k - (1 << i) <= year2:
            count += 1
    x += 1

print count

Submission: http://codeforces.com/contest/611/submission/15230069

Upvotes: 2

Related Questions