Untitled

from collections import deque, defaultdict
import heapq


class GraphAlgorithms:
    def __init__(self, n):
        self.n = n
        self.adj = defaultdict(list)

    def add_edge(self, u, v, weight=1, directed=False):
        self.adj[u].append((v, weight))
        if not directed:
            self.adj[v].append((u, weight))

    def bfs(self, start):
        visited = [False] * self.n
        queue = deque([start])
        visited[start] = True
        bfs_order = []

        while queue:
            node = queue.popleft()
            bfs_order.append(node)
            for neighbor, _ in self.adj[node]:
                if not visited[neighbor]:
                    queue.append(neighbor)
                    visited[neighbor] = True
        return bfs_order

    def dfs(self, start):
        visited = [False] * self.n
        dfs_order = []

        def _dfs(node):
            visited[node] = True
            dfs_order.append(node)
            for neighbor, _ in self.adj[node]:
                if not visited[neighbor]:
                    _dfs(neighbor)

        _dfs(start)
        return dfs_order

    def dijkstra(self, start):
        distances = {i: float('inf') for i in range(self.n)}
        distances[start] = 0
        priority_queue = [(0, start)]

        while priority_queue:
            current_distance, current_node = heapq.heappop(priority_queue)
            if current_distance > distances[current_node]:
                continue
            for neighbor, weight in self.adj[current_node]:
                distance = current_distance + weight
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    heapq.heappush(priority_queue, (distance, neighbor))

        return distances

    def bellman_ford(self, start):
        distances = [float('inf')] * self.n
        distances[start] = 0
        for _ in range(self.n - 1):
            for u in self.adj:
                for v, weight in self.adj[u]:
                    if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                        distances[v] = distances[u] + weight
        # Check for negative-weight cycles
        for u in self.adj:
            for v, weight in self.adj[u]:
                if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                    return "Graph contains a negative-weight cycle"
        return distances

    def floyd_warshall(self):
        dist = [[float('inf')] * self.n for _ in range(self.n)]
        for i in range(self.n):
            dist[i][i] = 0
        for u in self.adj:
            for v, weight in self.adj[u]:
                dist[u][v] = weight
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        return dist

    def kruskal(self, edges):
        def find(parent, i):
            if parent[i] == i:
                return i
            return find(parent, parent[i])

        def union(parent, rank, x, y):
            root_x = find(parent, x)
            root_y = find(parent, y)
            if rank[root_x] < rank[root_y]:
                parent[root_x] = root_y
            elif rank[root_x] > rank[root_y]:
                parent[root_y] = root_x
            else:
                parent[root_y] = root_x
                rank[root_x] += 1

        edges.sort(key=lambda x: x[2])
        parent = [i for i in range(self.n)]
        rank = [0] * self.n
        mst = []
        mst_weight = 0

        for u, v, weight in edges:
            root_u = find(parent, u)
            root_v = find(parent, v)
            if root_u != root_v:
                mst.append((u, v, weight))
                mst_weight += weight
                union(parent, rank, root_u, root_v)

        return mst, mst_weight

    def prim(self):
        visited = [False] * self.n
        min_heap = [(0, 0)]  # (weight, vertex)
        mst_weight = 0
        mst_edges = []

        while min_heap:
            weight, u = heapq.heappop(min_heap)
            if visited[u]:
                continue
            visited[u] = True
            mst_weight += weight
            for v, w in self.adj[u]:
                if not visited[v]:
                    heapq.heappush(min_heap, (w, v))
                    mst_edges.append((u, v, w))

        if all(visited):
            return mst_edges, mst_weight
        else:
            return None  # MST does not exist

    def kosaraju(self):
        def dfs(v, visited, stack):
            visited[v] = True
            for u, _ in self.adj[v]:
                if not visited[u]:
                    dfs(u, visited, stack)
            stack.append(v)

        def dfs_rev(v, visited, component):
            visited[v] = True
            component.append(v)
            for u, _ in reversed_adj[v]:
                if not visited[u]:
                    dfs_rev(u, visited, component)

        stack = []
        visited = [False] * self.n
        for i in range(self.n):
            if not visited[i]:
                dfs(i, visited, stack)

        reversed_adj = defaultdict(list)
        for u in self.adj:
            for v, _ in self.adj[u]:
                reversed_adj[v].append((u, 1))

        visited = [False] * self.n
        scc = []
        while stack:
            v = stack.pop()
            if not visited[v]:
                component = []
                dfs_rev(v, visited, component)
                scc.append(component)

        return scc

    def traveling_salesman(self, graph):
        dp = [[None] * (1 << self.n) for _ in range(self.n)]

        def tsp(pos, mask):
            if mask == (1 << self.n) - 1:
                return graph[pos][0]
            if dp[pos][mask] is not None:
                return dp[pos][mask]

            ans = float('inf')
            for city in range(self.n):
                if mask & (1 << city) == 0:
                    ans = min(ans, graph[pos][city] +
                              tsp(city, mask | (1 << city)))
            dp[pos][mask] = ans
            return ans

        return tsp(0, 1)
    
    def largestBst(self, root):
        #code here
        max_size=0
        def check_Bst(root,larger,smaller):
            nonlocal max_size
            if root is None:
                return True,0
            larger=max(root.data,larger)
            smaller=min(smaller,root.data)
            left,a=check_Bst(root.left,larger,root.data)
            right,b=check_Bst(root.right,root.data,smaller)
            max_size=max(max_size,max(a,b))
            if left and right:
                if root.data>larger and root.data<smaller:
                    if root.left and root.right:
                        if root.data>root.left.data and root.data<root.right.data:
                            return True,1+a+b
                        else:
                            return False,0
                    if root.left and root.right is None:
                        if root.data>root.left.data :
                            return True,1+a
                        else:
                            return False,0
                    if root.right and root.left is None:
                        if root.data<root.right.data :
                            return True,1+b
                        else:
                            return False,0
                    elif root.left is None and root.right is None:
                        return True,1
                else:
                    return False,0
            else:
                return False,0
        
        _,a=check_Bst(root,float('-inf'),float('inf'))
        return max(max_size,a)


class TrieNode:
    def __init__(self):
        self.childNode = [None] * 26
        self.wordEnd = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, string):
        curr_node = self.root
        for c in string:
            if curr_node.childNode[ord(c)-ord('a')] is None:
                node = TrieNode()
                curr_node.childNode[ord(c)-ord('a')] = node

            curr_node = curr_node.childNode[ord(c)-ord('a')]
        curr_node.wordEnd = True

    def search(self, key):
        curr_node = self.root
        for c in key:
            if curr_node.childNode[ord(c)-ord('a')] is None:
                return False
            curr_node = curr_node.childNode[ord(c)-ord('a')]
        return curr_node.wordEnd

    def delete(self, key):
        def dele(root, key, index):
            if index == len(key) and root.wordEnd:
                return None
            if root.childNode[ord(key[index])-ord('a')]:
                root.childnode[ord(
                    key[index])-ord('a')] = dele(root.childNode[ord(key[index])-ord('a')], key, index+1)
                if root.wordEnd == False:
                    return None
            return root
        self.root = dele(self.root, key, 0)

    def wordBreak(self, key):
        def check(root, key, i):
            if i == len(key):
                return root.wordEnd
            if root.childNode[ord(key[i])-ord('a')] is None:
                return False
            if root.childNode[ord(key[i])-ord('a')].wordEnd:
                if check(self.root, key, i+1):
                    return True
            return check(root.childNode[ord(key[i])-ord('a')], key, i+1)
        return 1 if check(self.root, key, 0) else 0

    def wordBreak_dp(self, key):
        dp = [False]*(len(key)+1)
        dp[0] = 1

        for i in range(1, len(key)+1):
            for j in range(i-1, -1, -1):
                if dp[j] and self.search(key[j:i]):
                    dp[i] = True
                    break

        return dp[len(key)]


class DynamicProgramming:
    def __init__(self) -> None:
        pass

    def Longest_increasing_subarray(self, nums):
        # basic approach we maintain a dp to write the max length of increasing subarray till index i as 1 initially
        #  then we go backwards from each index that is from 0 to 0 1 to 0 n-1 to 0
        # since we are going backwards we need to check if a num is smaller than the one we are going back from and update the dp value if the value is smaller than
        dp = [1]*len(nums)
        for i in range(0, len(nums)):
            for j in range(0, i):
                if nums[i] > nums[j] and dp[j]+1 > dp[i]:
                    dp[i] = dp[j]+1
        # same can be used for any kind of longest subsequence with just changing the condition
        return max(dp)

    def catalan(self, n):
        # Base Case
        if n <= 1:
            return 1

        # Catalan(n) is the sum
        # of catalan(i)*catalan(n-i-1)
        res = 0
        for i in range(n):
            res += self.catalan(i) * self.catalan(n-i-1)

        return res

    def longest_common_subsequence(self, text1, text2):
        dp = [[0 for _ in range(len(text1)+1)] for _ in range(len(text2)+1)]

        for i in range(1, len(text2)+1):
            for j in range(1, len(text1)+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

        return dp[len(text2)][len(text1)]

    def editDistance(self,text1,text2):
        dp = [[0 for _ in range(len(text1)+1)] for _ in range(len(text2)+1)]
        dp[0][0]=0
        for i in range(1, len(text2)+1):
            dp[i][0]=i
                      
        for j in range(1, len(text1)+1):
            dp[0][j]=j

        for i in range(1, len(text2)+1):
            for j in range(1, len(text1)+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j], dp[i][j-1]))+1

        return dp[len(text2)][len(text1)]
  
    def equal_sum_partition(self,arr):
        total_sum=0
        for num in arr:
            total_sum+=num
        if total_sum%2==1:
            return False
        dp=[False for _ in range((total_sum//2)+1)]
        dp[0]=True
        for i in range(len(arr)):
            for S in range(total_sum//2,arr[i]-1,-1):
                if dp[S-arr[i]]:
                    dp[S]=True
        
        return dp[total_sum//2]
 
    def circular_houseRobbery(self,arr):
        dp=[num for num in arr]
        n=len(arr)
        if len(arr)>1:
            # start from 0
            dp[1]=max(dp[1],dp[0])
            for i in range(2,n-1):
                dp[i]=max(dp[i-1],dp[i-2]+dp[i])
            
            m1=max(dp)
            dp=[num for num in arr]
            
            # starting from 1
            dp[2]=max(dp[1],dp[2])
            for i in range(3,n):
                dp[i]=max(dp[i-1],dp[i-2]+dp[i])
            m2=max(dp)
            return max(m1,m2) 
        return max(dp)
  
    def longestPalinSubseq(self, S):
        # just longest common substring in string and reverse
        dp=[[-1 for _ in range(len(S)+1)] for _ in range(len(S)+1)]
        
        for i in range(len(S)+1):
            dp[i][0]=0
            dp[0][i]=0
        
        rev=""
        for l in S:
            rev+=l
        rev=rev[::-1]
        
        for i in range(1,len(S)+1):
            for j in range(1,len(S)+1):
                if S[i-1]==rev[j-1]:
                    dp[i][j]=dp[i-1][j-1]+1
                else:
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        
        return dp[len(S)][len(S)]

    def longest_repeating_subsequence(self,S):
        return self.longest_common_subsequence(S,S)        
        

class Greedy():
    def ActivitySelection(self,start,end):
        pairs=[]
        for i in range(len(start)):
            pairs.append([start[i],end[i]])
        
        pairs.sort(key=lambda x:x[1])
        
        end_time=pairs[0][1]
        activity=1
        for i in range(1,len(pairs)):
            if pairs[i][0]>end_time:
                activity+=1
                end_time=pairs[i][1]
        return activity

    def minPartition(self, N):
        # code here
        coins=[1,2,5,10,20,50,100,200,500,2000]
        
        i=len(coins)-1
        ans=[]
        
        while N!=0:
            if N>=coins[i]:
                N-=coins[i]
                ans.append(coins[i])
            else:
                i-=1
        
        return ans
    
    def minSum(self, arr, n):
        if n==1:
            return arr[0]
        arr=sorted(arr)
        num1=''
        num2=''
        for i in range(n):
            if i%2==0:
                num1+=(str(arr[i]))
            else:
                num2+=(str(arr[i]))
        
        return int(num1)+int(num2)
    
    def fractionalknapsack(self, w,arr,n):
        for i in range(n):
            arr[i].value=float(arr[i].value/arr[i].weight)
            
        arr.sort(key=lambda x:x.value)
        arr.reverse()
        ans=0
        i=0
        while w and i<len(arr):
            if arr[i].weight<=w:
                ans+=arr[i].value*arr[i].weight
                w-=arr[i].weight
            else:
                ans+=arr[i].value*w
                w-=w
            i+=1
        
        return ans
        # code here
   
     
    # vszjvnlnvc