[Python] How to generate an integer that repeats like 100100100…1 in binary with time...

I am making a function that takes length:int and distance:int as inputs, and output the largest integer that satisfies the following properties in its binary representation:

1. 
   It starts with 1, ends with 1
   
   
2. 
   There are distance - 1 many 0 between each 1
   
   
3. 
   Its length is strictly less than length
   

It could be implemented as the following:

def repeatdigit(length:int, distance:int) -> int:
result = 0
pointer = 1
for _ in range(1, length, distance):
result |= pointer
pointer <<= scale
return result


For example: repeatdigit(10,3)==0b1001001 , repeatdigit(15,4)=0b1000100010001. I’m only caring about binary because I need to use it as a tool of bit manipulation. In practice, length will be very big, distance ** 2 < length. Assuming the input is valid.

As its name suggested, it is repeating a same pattern over and over.

An explicit formula:

result = (1 << (length - (length % distance)))//((1 << distance) - 1)


But both algorithm are slow, their time complexity is O(n²), where n = length.

Doing similar things with list only takes O(n). Namely ([1]+[0]*(distance-1)) * (length//distance) + [1]

(Context: I want to make such an integer so that I don’t need to store 0 and 1 in a very long list as it is space consuming)

How do I make such an integer in O(n)?

Continue reading...