from math import sqrt
def sieve_prime(num):
    prime_arr = [1] * (num+1) 
    prime_arr[0] = 0 
    prime_arr[1] = 0 
    for i in range(2, int(sqrt(num))+1):
        if prime_arr[i] == 1:
            j=2
            while i*j<num+1:
                prime_arr[j*i] = 0
                j+=1
    return prime_arr

print(sieve_prime(15))

from math import sqrt
def check_Prime(num):
    if num>1:
        for i in range(2, int(sqrt(num/2))):
            if(num%i==0):
                return(f"{num} is Not Prime")
            return(f"{num} is Prime")
    
print(check_Prime(18))

def max_sum_SubArray(arr):
    current_sum = 0
    max_so_far = arr[0]
    for i in range(len(arr)):
        current_sum = current_sum + arr[i]
        if max_so_far < current_sum:
            max_so_far = current_sum
        elif current_sum < 0:
            current_sum = 0
    return max_so_far

arr = [4, -3, -2, 2, 3, 1, -2, -3, 6, -6, -4, 2, 1]
print(max_sum_SubArray(arr))

def length():
    string = input("Enter the stirng : ").split()
    last_word = len(string[-1])
    print(last_word)

length()

def remove_duplicates(arr):
    arr = sorted(arr)
    # print(arr)
    rmv_dpl = list(set(arr))
    return rmv_dpl

a = [9, 7, 5, 8, 6, 1, 2, 4, 3, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(remove_duplicates(a))

def hotel_booking(arr, dept, room):
    event = [(t, 'RED') for t in arr] + [(t, "BLUE") for t in dept]
    event = sorted(event)
    
    guest = 0
    for e in event:
        if e[1] == 'RED':
            guest+=1
        else:
            guest-=1
        
        if guest > room:
            return 'Sorry the rooms are full'
    return 'Rooms available'

arr = [1, 3, 5]
dept = [2, 6, 8]
k = 1

print(hotel_booking(arr, dept, k))

def wave(arr):
    size = len(arr)
    for index in range(0, size, 2):
        if index > 0 and arr[index-1] > arr[index]:
            arr[index-1], arr[index] = arr[index], arr[index-1]
        elif index < size - 1 and arr[index] < arr[index+1]:
            arr[index], arr[index+1] = arr[index+1], arr[index]

    return arr

arr = [3, 5, 12, 2, 6, 10, 7, 9, 8]
print(wave(arr))

def rain_water_trap(arr):
    size = len(arr)
    left = size * [0]
    right = size * [0]
    left[0] = arr[0]
    max_so_far_left = arr[0]
    water = 0

    for index in range(size):
        if max_so_far_left < arr[index]:
            max_so_far_left = arr[index]
            left[index] = max_so_far_left
        else:
            left[index] = max_so_far_left
     
    max_so_far_right = arr[-1]

    for index in range(size-1, -1, -1):
        if max_so_far_right < arr[index]:
            max_so_far_right = arr[index]
            right[index] = max_so_far_right
        else:
            right[index] = max_so_far_right

    for index in range(size):
        water = water + min(left[index],right[index]) - arr[index]

    return water

list1 = [1, 0, 2, 0, 1, 0, 3, 1, 0, 2]
print(rain_water_trap(list1))

def postfix(arr):
    stack = []
    operators = ['+', '-', '*', '/', '%']
    for item in arr:
        if item not in operators:
            stack.append(item)
        else:
            first = int(stack.pop())
            second = int(stack.pop())

            if(item == '+'):
                stack.append(second + first)
            elif(item == '-'):
                stack.append(second - first)
            elif(item == '*'):
                stack.append(second * first)
            elif(item == '/'):
                stack.append(second / first)
            elif(item == '%'):
                stack.append(second % first)
    return stack[-1]

arr = ['2', '1', '+', '3', '5', '+', '*']
print(postfix(arr))