# time needed to generate MicroMint coins.
# balls-and-bins problem
# parameter: u = number of bits used for identifying the bin. b = 2^u
# parameter: k = number of collisions (balls in the same bin) needed to make a coin. Fewer than k balls in the bin makes no coins. k or more balls in a bin makes precisely one coin.
# how many iterations(how many balls thrown) does it take before you generate c = 1, 100, and 10 000 coins respectively?
# all bins are empy at first. At each iteration, throw a ball into a randomly selected bin.
# use t = 0

import random
import math

lamda = 3.66

# input values
u = 20
k = 7
c = 10000
width = 4783
times = 10

min_v = 0
max_v = 0


# balls in bins problem until coins == c
def make_coins(u, k, c):
    global min_v
    global max_v

    b = 2 ** u
    bins = [0] * b
    iterations = 0
    coins = 0
    while coins < c:
        r = random.randint(0, len(bins) - 1)
        bins[r] += 1
        if bins[r] == k:
            coins += 1
        iterations += 1

    if iterations < min_v:
        min_v = iterations
    elif iterations > max_v:
        max_v = iterations
    return iterations


# mean calculation
def mean_value(times):
    i_sum = 0
    i = 0
    for i in range(times):
        i_sum += make_coins(u, k, c)

    return i_sum / times


mean_v = mean_value(times)
diff = max_v - min_v
deviation = math.sqrt(diff)
check = 3.66 * deviation / math.sqrt(times)

if(check < width):
    print(mean_v)
else:
    print("Outside confidence intervall")