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:
-
It starts with
1, ends with1 -
There are
distance - 1many0between each1 -
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 <<= distance
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+distance-2 - ((length-2) % 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-2)//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)?
9
Doubling the number of 1-bits instead of adding them just one at a time:
def repeatdigit(length:int, distance:int) -> int:
def f(want):
if want == 1:
return 1
have = (want + 1) // 2
x = f(have)
add = min(have, want - have)
return x | (x << (add * distance))
ones = 1 + (length - 2) // distance
return f(ones)
My ones, want, have and add refer to numbers of 1-bits.
The add = min(have, want - have) could be “simplified”, as I either add have or have - 1 1-bits. It comes from this earlier, slightly less optimal version:
def repeatdigit(length:int, distance:int) -> int:
result = 1
want = 1 + (length-2) // distance
have = 1
while have < want:
add = min(have, want - have)
result |= result << (add * distance)
have += add
return result
2