#--------------------------------topic: --------------------------------#




#################################Slide 8#######################################
def solveMissingPuzzle(data):
  _missingdata = [ [] ]*(9)
  for i in range(0, 9):
    _missingdata[i] = [ [] ]*(9)
    for j in range(0, 9):
      if data[i][j] == 0:
        _missingdata[i][j] = set( range(1, 10) )

    for i in range(0, 9):
      for j in range(0, 9):
        if data[i][j] == 0:
          for k in range(0, 9):
            _missingdata[i][j].discard ( data[k][j] )
            _missingdata[i][j].discard ( data[i][k] )

          for l in range(0, 3):
            for m in range(0, 3):
              _missingdata[i][j].discard( 
                   data[3 * int(i/3) + l][3 * int(j/3) + m] )

          if len(_missingdata[i][j]) == 1:
            data[i][j] = _missingdata[i][j].pop()



#--------------------------------topic: --------------------------------#




#################################Slide 2#######################################
n = 100

sum = 0
for i in range(0, n):
    sum += i
print("sum is: ", sum)



#################################Slide 3#######################################
n = 100

sum = 0
for i in range(0, n):
    sum += i
print("sum is: ", sum)



#################################Slide 4#######################################
n = 100

sum = 0
for i in range(0, 100):
    sum += i
print("sum is: ", sum)



#################################Slide 5#######################################
import time

n = pow(10,5)

start_time = time.time()

sum = 0
for i in range(0, n):
    sum += i

end_time = time.time()
print("time: ", end_time - start_time)



#################################Slide 5#######################################
import time

n = pow(10,6)

start_time = time.time()

sum = 0
for i in range(0, n):
    sum += i

end_time = time.time()
print("time: ", end_time - start_time)



#################################Slide 5#######################################
import time

n = pow(10,7)

start_time = time.time()

sum = 0
for i in range(0, n):
    sum += i

end_time = time.time()
print("time: ", end_time - start_time)



#################################Slide 6#######################################
import time

for p in range(1, 100):

    n = pow(10,p)

    start_time = time.time()

    sum = 0
    for i in range(0, n):
        sum += i

    end_time = time.time()




#--------------------------------topic: --------------------------------#




#################################Slide 3#######################################
def find(A, x):
  n = len(A)
  
  for i in range(0, n):
    if x == A[i]:
      return True

  return False



#################################Slide 15#######################################
def binarySearch(A, x):
    start, end = 0, len(A)-1

    while end >= start:
        mid = (start+end)//2
        if x == A[mid]:
            return mid
        if x > A[mid]:
            start = mid+1
        if x < A[mid]:
            end = mid-1
    return False

import random
A = sorted( [ random.randint(0,20) for _ in range(0,10) ] )
print(A)

x = 4
print(f"Is {x} in A: ", binarySearch(A, x))




#################################Slide 16#######################################
def binarySearch_RECURSIVE(A, start, end, x):
    if end < start:
        return None

    mid = (start+end) // 2
    if x == A[mid]:
        return mid
    if x < A[mid]:
        return binarySearch_RECURSIVE(A, start, mid-1, x)
    else:
        return binarySearch_RECURSIVE(A, mid+1, end, x)

import random
A = sorted( [ random.randint(0,20) for _ in range(0,10) ] )
print(A)

x = 4
print(f"Is {x} in A:",binarySearch_RECURSIVE(A,0,len(A)-1, x))




#################################Slide 17#######################################
import time, random, math

def binarySearch(A, x):
    start, end = 0, len(A)-1

    while (end-start)>=0:
        mid = (start+end) // 2
        if x == A[mid]:
            return mid
        elif x > A[mid]:
            start = mid+1
        elif x < A[mid]:
            end = mid-1
    return -1

n = 100000000
A = sorted([ random.randint(0, 20) for _ in range(0, n) ])

start = time.time()
ans = binarySearch(A, 6)
binarySearch_time = time.time() - start

start = time.time()
ans3 = 6 in A
IN_time = time.time() - start

print(f"Time for binarySearch: {binarySearch_time:f}")
print(f"Time for IN: {IN_time:f}")




#################################Slide 27#######################################
import math

def mysqrt(S):
    start = 1
    end = S

    for i in range(0, int(math.log2(S)) + 1):
        m = (start + end) / 2.0

        if m * m == S:
            return int(m)
        elif m * m < S:
            start = m
        else:
            end = m

    if ( int(end)*int(end) > S ):
        return int(start)
    else:
        return int(end)

print( mysqrt(22) )





#################################Slide 28#######################################
def mysqrt(x, k):
    start = 1
    end = x

    for i in range(0, k):
        m = (start+end)/2.0

        if x == m*m:
            return m
        elif x < m*m:
            end = m
        elif x > m*m:
            start = m

    return (start+end)/2.0

for i in range(1, 10):
    print(f"k={i}: {mysqrt(22, i)}")




#################################Slide 36#######################################
def count_pieces(woods, L):
    total = 0
    for w in woods:
        total += w // L
    return total

def max_wood_length(woods, k):
    if sum(woods) < k:
        return 0 
    
    left, right = 1, max(woods)
    answer = 0
    
    while left <= right:
        mid = (left + right) // 2
        if count_pieces(woods, mid) >= k:
            answer = mid  
            left = mid + 1
        else:
            right = mid - 1 
    
    return answer

woods = [20, 15, 10, 17]
k = 7
print(max_wood_length(woods, k))