Python_DSA_Day4.txt

"""
Given an array of sorted integers. We need to find the closest value to the 
given number.

Array may contain duplicate values and negative numbers.

Examples:

    Input : arr[] = {1, 2, 4, 5, 6, 6, 8, 9}

    Target number = 11
    Output : 9
    9 is closest to 11 in given array

    Input :arr[] = {2, 5, 6, 7, 8, 8, 9};
    Target number = 4
    Output : 5
"""

A = [1, 2, 4, 5, 6, 6, 8, 9]
A = [2, 5, 6, 7, 8, 8, 9]


def find_closest_num(A, target):
    min_diff = float("inf")
    low = 0
    high = len(A) - 1
    closest_num = None

    # Edge cases for empty list of list
    # with only one element:
    if len(A) == 0:
        return None
    if len(A) == 1:
        return A[0]

    while low <= high:
        mid = (low + high)//2

        # Ensure you do not read beyond the bounds
        # of the list.
        if mid+1 < len(A):
            min_diff_right = abs(A[mid + 1] - target)
        if mid > 0:
            min_diff_left = abs(A[mid - 1] - target)

        # Check if the absolute value between left
        # and right elements are smaller than any
        # seen prior.
        if min_diff_left < min_diff:
            min_diff = min_diff_left
            closest_num = A[mid - 1]

        if min_diff_right < min_diff:
            min_diff = min_diff_right
            closest_num = A[mid + 1]

        # Move the mid-point appropriately as is done
        # via binary search.
        if A[mid] < target:
            low = mid + 1
        elif A[mid] > target:
            high = mid - 1
        # If the element itself is the target, the closest
        # number to it is itself. Return the number.
        else:
            return A[mid]
    return closest_num


y = find_closest_num(A, 4)
print(y)



##2 
'''
Input: arr[] = {-10, -5, 0, 3, 7}
  Output: 3  // arr[3] == 3 

  Input: arr[] = {0, 2, 5, 8, 17}
  Output: 0  // arr[0] == 0 


  Input: arr[] = {-10, -5, 3, 4, 7, 9}
  Output: -1  // No Fixed Point
'''

#LOGIC: 
'''
First check whether middle element is Fixed Point or not.
If it is, then return it; otherwise check whether index of 
middle element is greater than value at the index. If index 
is greater, then Fixed Point(s) lies on the right side of the 
middle point (obviously only if there is a Fixed Point). 
Else the Fixed Point(s) lies on left side.
'''  

# Python program to check fixed point 
# in an array using binary search 
def binarySearch(arr, low, high): 
	if high >= low: 
		mid = (low + high)//2
	
	if mid is arr[mid]: 
		return mid 
	
	if mid > arr[mid]: 
		return binarySearch(arr, (mid + 1), high) 
	else: 
		return binarySearch(arr, low, (mid -1)) 
	
	# Return -1 if there is no Fixed Point 
	return -1


# Driver program to check above functions */ 
arr = [-10, -1, 0, 3, 10, 11, 30, 50, 100] 
n = len(arr) 
print("Fixed Point is " + str(binarySearch(arr, 0, n-1))) 

###2 Kth element in 2 arrays


def kthElement(a,b,k):
    i = k//2
    j = k - i
    step = k//4
    while step > 0:
        if a[i-1] > b[j-1]:
            i -= step
            j += step
        else:
            i += step
            j -= step
        step //= 2
    
    if a[i-1] > b[j-1]:
        return a[i-1]
    else:
        return b[j-1]


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


##3 FIND MAX IN ARR WHICH IS FIRST INC AND THEN DEC

def findMaximum(nums): 
    left = 0
    right = len(nums)-1
    while(left<right):
        mid = (left+right)//2
        if nums[mid] > nums[mid+1]:
            right = mid
        else:
            left = mid+1
    return arr[left]  
        
# Driver program to check above functions */ 
arr = [1, 3, 50, 10, 9, 7, 6] 
n = len(arr) 
print (findMaximum(arr)) 

OUTPUT = 50


##5 The painter’s partition problem or Book/Page alocation problem / ship capacity in D daya

def shipWithinDays(self, weights: List[int], D: int) -> int:
        def leastweight(cap, weights, D):
            out = 0
            curr_cap = cap
            for w in weights:
                if curr_cap >= w:
                    curr_cap = curr_cap-w
                else:
                    out+=1
                    curr_cap = cap
                    curr_cap = curr_cap-w
            
            return (out+1) <=D
            
        
        low = max(weights)
        high = sum(weights)
        
        while(low<high):
            mid = low + (high-low)//2
            if leastweight(mid, weights, D):
                high = mid
            else:
                low = mid+1
        return low