Annettuna on lista, jossa on kokonaislukuja. Tehtäväsi on muodostaa mahdollisimman monta paria, jossa suurempi luku on vähintään kaksinkertainen pienempään nähden. Jokainen luku voi kuulua enintään yhteen pariin.
Tarkemmin sanoen pari on kelvollinen pari, jos pätee ehto .
Esimerkiksi kun lista on , voidaan muodostaa enintään kaksi paria. Yksi mahdollinen ratkaisu on valita parit ja .
Toteuta tiedostoon bigsmall.py
funktio count_pairs
, jolle annetaan lista lukuja. Jokainen listan luku on positiivinen kokonaisluku. Funktion tulee palauttaa suurin mahdollinen parien määrä.
Sinun tulee toteuttaa funktio niin, että se laskee vastauksen tehokkaasti myös suurelle listalle. Funktion tulee antaa vastaus välittömästi myös tehtäväpohjan viimeisessä testissä.
def count_pairs(numbers): # TODO if __name__ == "__main__": print(count_pairs([1])) # 0 print(count_pairs([1, 2, 3])) # 1 print(count_pairs([1, 2, 3, 4])) # 2 print(count_pairs([1, 1, 1, 1])) # 0 print(count_pairs([10**9, 1, 1, 1])) # 1 print(count_pairs([4, 5, 1, 4, 7, 8])) # 2 print(count_pairs([1, 2, 3, 2, 4, 6])) # 3 numbers = [(x * 999983) % 10**6 + 1 for x in range(10**5)] print(count_pairs(numbers)) # 41176