I tried to count ones in binary list It takes integer input and converts it to list(i.e. input=3,[1,2,3]) Then i wanted to change int to binary and count how many "1" are in list.
My code:
a=int(input())
y=[x for x in range(0,a+1)]
for i in range(1,a+1):
y[i]=format(i,"b").count('1')
print(sum(y))
It works fine, but it uses too much memory for big number(562949953421310), so i got runtime error. How could i make it use less memory/run faster?
You can do without using the list as storing the list of elements takes a lot of memory. Instead count without using the list. Try in this way
a = int(input())
count = 0
for i in range(1,a+1):
count += format(i,"b").count('1')
print(count)
You can try this:
def count_1_in_bin(n):
count = 0
for i in range(1, n + 1):
count += bin(i).count("1")
return count
If you have python 3.10 then try this:
def count_1_in_bin(n):
count = 0
for i in range(1, n + 1):
count += i.bit_count()
return count
def count_1_in_bin(n) :
n += 1
power_of_2 = 2
count = n // 2
while (power_of_2 <= n):
totalPairs = n // power_of_2
count += (totalPairs // 2) * power_of_2
if (totalPairs & 1):
count += (n % power_of_2)
else:
count += 0
power_of_2 <<= 1
return count
Pattern Recognition Approach:
Let n be any arbitrary number and consider indexing from right to left(rightmost being 1); then nearest_pow = pow(2,i).
Now, when you write all numbers from 1 to N, you will observe the pattern mentioned below:
For every index i, there are exactly nearest_pow/2 continuous elements that are unset followed by nearest_pow/2 elements that are set.
Throughout the solution, i am going to use this concept.
You can clearly observe above concept in the above table.
The general formula:
a. add_remaining = mod – (nearest_pow/2) + 1 if mod >= nearest_pow/2
b. total_set_bit_count = totalRep*(nearest_pow/2) + add_remaining
where,
totalRep -> total number of times the pattern repeats at index i
add_remaining -> total number of set bits left to be added after the pattern is exhausted
Let N = 17:
leftMostSetIndex = 5 (Left most set bit index, considering 1 based indexing)
i = 1 => nearest_pow = pow(2,1) = 2; totalRep = (17+1)/2 = 9 (add 1 only for i=1)
mod = 17%2 = 1
add_remaining = 0 (only for base case)
total_set_bit_count = totalRep*(nearest_pow/2) + add_remaining = 9*(2/2) + 0 = 9*1 + 0 = 9
i = 2 => nearest_pow = pow(2, 2)=4; totalRep = 17/4 = 4
mod = 17%4 = 1
mod(1) < (4/2) => 1 < 2 => add_remaining = 0
total_set_bit_count = 9 + 4*(2) + 0 = 9 + 8 = 17
i = 3 => nearest_pow = pow(2,3) = 8; totalRep = 17/8 = 2
mod = 17%8 = 1
mod < 4 => add_remaining = 0
total_set_bit_count = 17 + 2*(4) + 0 = 17 + 8 + 0 = 25
i = 4 => nearest_pow = pow(2, 4) = 16; totalRep = 17/16 = 1
mod = 17%16 = 1
mod < 8 => add_remaining = 0
total_set_bit_count = 25 + 1*(8) + 0 = 25 + 8 + 0 = 33
We cannot simply operate on the next power(32) as 32>17. Also, as the first half bits will be 0s only, we need to find the distance of the given number(17) from the last power to directly get the number of 1s to be added
i = 5 => nearest_pow = (2, 5) = 32 (base case 2)
last_pow = pow(2, 4) = 16
mod = 17%16 = 1
total_set_bit_count = 33 + (mod+1) = 33 + 1 + 1 = 35
Therefore, total number of set bits from 1 to 17 is 35
Complete Code:
def get_left_most_set_bit(n):
left_most_set_bit_indx = 0
while n > 0:
left_most_set_bit_indx += 1
n >>= 1
return left_most_set_bit_indx
def total_set_bits_from_1_to_n(n):
left_most_set_bit_indx = get_left_most_set_bit(n)
total_rep = 0
mod = 0
nearest_pow = 0
total_set_bit_count = 0
add_remaining = 0
curr=0 # denotes the number of set bits at index i
for i in range(1, left_most_set_bit_indx + 1):
nearest_pow = pow(2, i)
if nearest_pow > n:
last_pow = pow(2, i-1)
mod = n % last_pow
total_set_bit_count += mod + 1
else:
if i == 1 and n % 2 == 1:
total_rep = (n + 1) / nearest_pow
mod = nearest_pow % 2
add_remaining = 0
else:
total_rep = int(n / nearest_pow)
mod = n % nearest_pow
add_remaining = int(mod - (nearest_pow / 2) + 1) if mod >= nearest_pow / 2 else 0
curr = int(total_rep * (nearest_pow / 2) + add_remaining)
total_set_bit_count += curr
return total_set_bit_count
I just try to benchmark my approach and SAI's approach, mine is faster than SAI's one. You can check the benchmark below
Code:
from timeit import repeat
import random
def count_1_in_bin_sabil_v1(n):
count = 0
for i in range(1, n + 1):
count += bin(i).count("1")
return count
def count_1_in_bin_sabil_v2(n):
count = 0
for i in range(1, n + 1):
count += i.bit_count()
return count
def count_1_in_bin_sai(n):
count = 0
for i in range(1, n + 1):
count += format(i, "b").count('1')
return count
def baseline(lst):
pass
funcs = count_1_in_bin_sabil_v1, count_1_in_bin_sabil_v2, count_1_in_bin_sai, baseline
for _ in range(3):
n = random.randint(99999, 999999)
for func in funcs:
times = sorted(repeat(lambda: func(n), number=100))
print(*('%3d ms ' % (t * 1e3) for t in times), func.__name__)
print()
Benchmark Output:
14118 ms 14190 ms 14221 ms 14223 ms 14239 ms count_1_in_bin_sabil_v1
4591 ms 4593 ms 4662 ms 4692 ms 4694 ms count_1_in_bin_sabil_v2
19581 ms 19589 ms 19594 ms 19608 ms 19633 ms count_1_in_bin_sai
0 ms 0 ms 0 ms 0 ms 0 ms baseline
11312 ms 11318 ms 11330 ms 11330 ms 12269 ms count_1_in_bin_sabil_v1
3734 ms 3737 ms 3741 ms 3747 ms 3803 ms count_1_in_bin_sabil_v2
15970 ms 15971 ms 15975 ms 15987 ms 16811 ms count_1_in_bin_sai
0 ms 0 ms 0 ms 0 ms 0 ms baseline
2619 ms 2619 ms 2621 ms 2626 ms 2711 ms count_1_in_bin_sabil_v1
917 ms 918 ms 919 ms 920 ms 920 ms count_1_in_bin_sabil_v2
3753 ms 3754 ms 3767 ms 3782 ms 3813 ms count_1_in_bin_sai
0 ms 0 ms 0 ms 0 ms 0 ms baseline
Code:
from timeit import repeat
import random
def get_left_most_set_bit(n):
left_most_set_bit_indx = 0
while n > 0:
left_most_set_bit_indx += 1
n >>= 1
return left_most_set_bit_indx
def count_1_in_bin_sabil_v1(n):
left_most_set_bit_indx = get_left_most_set_bit(n)
total_rep = 0
mod = 0
nearest_pow = 0
total_set_bit_count = 0
add_remaining = 0
curr=0 # denotes the number of set bits at index i
for i in range(1, left_most_set_bit_indx + 1):
nearest_pow = pow(2, i)
if nearest_pow > n:
last_pow = pow(2, i-1)
mod = n % last_pow
total_set_bit_count += mod + 1
else:
if i == 1 and n % 2 == 1:
total_rep = (n + 1) / nearest_pow
mod = nearest_pow % 2
add_remaining = 0
else:
total_rep = int(n / nearest_pow)
mod = n % nearest_pow
add_remaining = int(mod - (nearest_pow / 2) + 1) if mod >= nearest_pow / 2 else 0
curr = int(total_rep * (nearest_pow / 2) + add_remaining)
total_set_bit_count += curr
return total_set_bit_count
def count_1_in_bin_sabil_v2(n) :
n += 1
power_of_2 = 2
count = n // 2
while (power_of_2 <= n):
totalPairs = n // power_of_2
count += (totalPairs // 2) * power_of_2
if (totalPairs & 1):
count += (n % power_of_2)
else:
count += 0
power_of_2 <<= 1
return count
def findLargestPower(n):
x = 0
while ((1 << x) <= n):
x += 1
return x - 1
def countSetBits(n):
if (n <= 1):
return n
x = findLargestPower(n)
return (x * pow(2, (x - 1))) + (n - pow(2, x) + 1) + countSetBits(n - pow(2, x))
def baseline(lst):
pass
funcs = count_1_in_bin_sabil_v1, count_1_in_bin_sabil_v2, countSetBits, baseline
for _ in range(3):
n = random.randint(2 ** 300, 2 ** 350)
print(f'N = {n}')
for func in funcs:
times = sorted(repeat(lambda: func(n), number=100))
print(*('%3d ms ' % (t * 1e3) for t in times), func.__name__)
print()
O(log(N)) Benchmark Output:
N = 2146035491051682585754446836731528113522426971225880134623415909538039007008682369107021328563978681517127
52 ms 52 ms 53 ms 53 ms 54 ms count_1_in_bin_sabil_v1
20 ms 20 ms 20 ms 20 ms 20 ms count_1_in_bin_sabil_v2
202 ms 202 ms 203 ms 205 ms 206 ms countSetBits
0 ms 0 ms 0 ms 0 ms 0 ms baseline
N = 1138923858983693003592575972830372018334926821729405331270636714881743472757989086033697436198972693705725
53 ms 53 ms 54 ms 54 ms 54 ms count_1_in_bin_sabil_v1
20 ms 20 ms 20 ms 20 ms 20 ms count_1_in_bin_sabil_v2
195 ms 197 ms 197 ms 197 ms 201 ms countSetBits
0 ms 0 ms 0 ms 0 ms 0 ms baseline
N = 1184515046889302539202909605775188852719875811827045009538443861363139355483601575331159905615000274858488
52 ms 52 ms 52 ms 52 ms 53 ms count_1_in_bin_sabil_v1
20 ms 20 ms 20 ms 20 ms 20 ms count_1_in_bin_sabil_v2
187 ms 187 ms 188 ms 189 ms 191 ms countSetBits
0 ms 0 ms 0 ms 0 ms 0 ms baseline
In CSES Problem Set Counting Bits, which is the source of this problem, the constraints are:
This means:
The following solution, explained in Method 4 of Count total set bits in all numbers from 1 to n, is O(log(n)) in time and O(1) in space.
Code
def findLargestPower(n):
x = 0
while ((1 << x) <= n):
x += 1
return x - 1
def countSetBits(n):
if (n <= 1):
return n
x = findLargestPower(n)
return (x * pow(2, (x - 1))) + (n - pow(2, x) + 1) + countSetBits(n - pow(2, x))
Test
N = 562949953421310
print(f'{ countSetBits(N):,}')
# Output: 13,792,273,858,822,095
%timeit countSetBits(N)
# Result: 309 µs ± 74.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
13792273858822095