Counting ones in binary list

Question

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?

Answer 1

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)

Answer 2

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

OR

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

OR

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

OR

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

Benchmark Between Solutions

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

Benchmark Between O(log(N)) Solutions

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

Answer 3

In CSES Problem Set Counting Bits, which is the source of this problem, the constraints are:

• 1 <= n <= 10**15
• time limit: 1 second
• space limit: 512 Mbyte

This means:

• No solution which is O(n) is complexity will satisfy the time requirement
• No solution which is O(n) in space will satisfy the space requirement

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