題目描述
你就是一個(gè)畫家瘟忱！你現(xiàn)在想繪制一幅畫奥额，但是你現(xiàn)在沒有足夠顏色的顏料苫幢。為了讓問題簡單访诱，我們用正整數(shù)表示不同顏色的顏料。你知道這幅畫需要的n種顏色的顏料韩肝，你現(xiàn)在可以去商店購買一些顏料触菜，但是商店不能保證能供應(yīng)所有顏色的顏料，所以你需要自己混合一些顏料哀峻∥邢啵混合兩種不一樣的顏色A和顏色B顏料可以產(chǎn)生(A XOR B)這種顏色的顏料(新產(chǎn)生的顏料也可以用作繼續(xù)混合產(chǎn)生新的顏色,XOR表示異或操作)哲泊。本著勤儉節(jié)約的精神，你想購買更少的顏料就滿足要求催蝗，所以兼職程序員的你需要編程來計(jì)算出最少需要購買幾種顏色的顏料切威？
輸入描述:
第一行為繪制這幅畫需要的顏色種數(shù)n (1 ≤ n ≤ 50)第二行為n個(gè)數(shù)xi(1 ≤ xi≤ 1,000,000,000)，表示需要的各種顏料.
輸出描述:
輸出最少需要在商店購買的顏料顏色種數(shù)丙号，注意可能購買的顏色不一定會使用在畫中先朦，只是為了產(chǎn)生新的顏色。
示例1
輸入
3
1 7 3
輸出
3
算法提示: 每個(gè)數(shù)其實(shí)是一個(gè)32緯的向量犬缨， 所以題目要算的其實(shí)是這n組向量的極大線性無關(guān)向量的個(gè)數(shù)==>矩陣求秩
n = int(input())
colors = sorted(list(map(int, input().split())))
def get_highest_digit(number):
? ? count = 0
? ? while number > 0:
? ? ? ? number >>= 1
? ? ? ? count += 1
? ? return count
min_require = 0
while len(colors) > 1:
? ? largest1, largest2 = colors[-1], colors[-2]
? ? if get_highest_digit(largest1) == get_highest_digit(largest2):
? ? ? ? new_color = largest1 ^ largest2
? ? ? ? if new_color not in colors:
? ? ? ? ? ? colors.append(new_color)
? ? ? ? ? ? colors.sort()
? ? else:
? ? ? ? min_require += 1
? ? colors.pop()
print(min_require + len(colors))
