Card#0           Card#1            Card#2         Card#3           Card#4
1, 3,  5,  7      2, 3, 6, 7     4, 5, 6, 7     8, 9, 10,11      16, 17, 18, 19
9, 11, 13, 15    10,11,14,15     12,13,14,15    12,13,14,15      20, 21, 22, 23
17, 19, 21, 23   18,19,22,23     20,21,22,23    24,25,26,27      24, 25, 26, 27
25, 27, 29, 31    26,27,30,31   28,29,30,31    28,29,30,31      28, 29, 30, 31

This can Predict any number between 1 and 31. So it can predict the day of your birthday by telling the programmer, myself what cards does your number appear in. You take the first number of a card that the number appeared and and add the first numbers that appear on the card.
For Example:

Number I selected is 27. The #27 appears on cards #0,1,3,4. The corresponding first numbers that appears on each of the cards it would be #1 2 8 16 = 27

By knowing doing this arithmetic i believe we see a log(n) alglorithm being used since it cut the code in halves and completed in about 2-3 functions.

My question is how can I expand this array set by increasing the parameter number to create more sets of arrays that can be perfectly sorted and will produce an extra card more than #4. In other words how can I make this code prediction parameters wider and still execute O(log(n) linear.

CodePudding user response：

The way this works is really just binary encoding. A number exists on card n if its nth bit (from the right) is turned on.

So, for example, 19 = 10011₂, so it shows up on cards 0, 1, and 4.

Thus, if you want to make this system work for numbers 1..n, you just need the number of cards to be equal to the number of bits in n. Then, on each card, just include all numbers with that bit flipped on.

Here's a demo, but please take the time to think about how you would implement this first and then seek to understand my code, not copy it:

n = int(input())
digits = len(bin(n)) - 2

def get_card(place):
	card = []
	for x in range(1, n   1):
		if x & (1 << place):
			card.append(x)
	return card

for x in range(digits):
	print(f"Card {x   1}:", get_card(x))

Try it online!

I notice you mention a time complexity restriction as well. I haven't checked if my code conforms to that - my goal here is purely to just give a demo of what this might look like - there is probably a more efficient way to get the list of all numbers with that bit flipped on (although, I think this is actually O(n log n), but I'm not sure).