Leetcode with dani

t = int(input())
while t>0:
    t-=1
    lenght = int(input())
    arr1 = list(map(int,input().split()))
    arr2 = list(map(int,input().split()))
    hash1 = set()
    hash2 = set()
    for i in range(len(arr1)):
        hash1.add(arr1[i])
        hash2.add(arr2[i])
    if (len(hash2)<=1 and len(hash1) <=2 )or (len(hash1)<=1 and len(hash2) <=2 ):
        print("NO")
    else:
        print("YES")

cᵢ = aᵢ + bᵢ   (1 ≤ i ≤ n)

5
4
1 2 1 2
1 2 1 2
6
1 2 3 3 2 1
1 1 1 1 1 1
3
1 1 1
1 1 1
6
1 52 52 3 1 3
59 4 3 59 3 4
4
100 1 100 1
2 2 2 2

YES
YES
NO
YES
NO

class Solution:
    def intToRoman(self, num: int) -> str:
        roman = {1: "I", 5: "V", 10: "X", 50: "L", 100: "C", 500: "D", 1000: "M"}
        s = ""
        st = str(num)
        length = len(st)
        
        for ch in st:
            i = int(ch)
            # Calculate the current power of ten (e.g., 1000, 100, 10, 1)
            place = 10 ** (length - 1)
            if i == 4 or i == 9:
                # For subtractive cases, e.g., 4 -> "IV" and 9 -> "IX"
                s += roman[place] + roman[place * (i + 1)]
            else:
                if i >= 5:
                    s += roman[place * 5]
                    s += roman[place] * (i - 5)
                else:
                    s += roman[place] * i
            length -= 1
        return s

# Example usage:
if __name__ == '__main__':
    sol = Solution()
    print(sol.intToRoman(3749))  # Output: "MMMDCCXLIX"

class Solution:
    def intToRoman(self, num: int) -> str:
        # Define the mapping of integers to Roman numerals
        val = [
            1000, 900, 500, 400,
            100, 90, 50, 40,
            10, 9, 5, 4,
            1
        ]
        syms = [
            "M", "CM", "D", "CD",
            "C", "XC", "L", "XL",
            "X", "IX", "V", "IV",
            "I"
        ]
        
        roman_num = ''
        i = 0
        while num > 0:
            for _ in range(num // val[i]):
                roman_num += syms[i]
                num -= val[i]
            i += 1
        return roman_num

# Example usage:
sol = Solution()
print(sol.intToRoman(1994))  # Output: "MCMXCIV"

class Solution:
    def intToRoman(self, num: int) -> str:
        # Mapping of integer values to Roman numerals
        roman_map = {
            1000: 'M',
            900: 'CM',
            500: 'D',
            400: 'CD',
            100: 'C',
            90: 'XC',
            50: 'L',
            40: 'XL',
            10: 'X',
            9: 'IX',
            5: 'V',
            4: 'IV',
            1: 'I'
        }
        
        roman_numeral = ''
        
        for value in roman_map.keys():
            while num >= value:
                roman_numeral += roman_map[value]
                num -= value
        
        return roman_numeral

# Example usage:
sol = Solution()
print(sol.intToRoman(58))  # Output: "LVIII"

class Solution:
    def intToRoman(self, num: int) -> str:
        # Define the mapping of integers to Roman numerals
        roman_map = [
            (1000, 'M'),
            (900, 'CM'),
            (500, 'D'),
            (400, 'CD'),
            (100, 'C'),
            (90, 'XC'),
            (50, 'L'),
            (40, 'XL'),
            (10, 'X'),
            (9, 'IX'),
            (5, 'V'),
            (4, 'IV'),
            (1, 'I')
        ]
        
        def convert(n):
            if n == 0:
                return ""
            for value, symbol in roman_map:
                if n >= value:
                    return symbol + convert(n - value)
        
        return convert(num)

# Example usage:
sol = Solution()
print(sol.intToRoman(3))  # Output: "III"

x + 2x + 4x + … + 2ᵏ⁻¹x = n

7
3
6
7
21
28
999999999
999999984

1
2
1
7
4
333333333
333333328

t = int(input())
while t > 0:
    num = int(input())
    k = 3
    n = 4
    while num % k:
        k += n
        n *= 2
    print(num // k)

from typing import List

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        # Step 1: Define movement directions (North, East, South, West)
        directions = [(0,1), (1,0), (0,-1), (-1,0)]  
        x, y, max_dist, d = 0, 0, 0, 0  # Robot starts at (0,0), facing North
        
        # Step 2: Convert obstacles list into a set for quick lookups
        obstacle_set = set(map(tuple, obstacles))  

        # Step 3: Process each command
        for command in commands:
            if command == -2:  # Turn left
                d = (d - 1) % 4
            elif command == -1:  # Turn right
                d = (d + 1) % 4
            else:  # Move forward k steps
                for _ in range(command):
                    next_x, next_y = x + directions[d][0], y + directions[d][1]
                    
                    # Stop moving if an obstacle is hit
                    if (next_x, next_y) in obstacle_set:
                        break  
                    
                    x, y = next_x, next_y  # Update position
                    max_dist = max(max_dist, x*x + y*y)  # Update max distance
        
        return max_dist  # Return max squared Euclidean distance

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        # Step 1: Compute prefix sum
        p = [0]  # Prefix sum array initialized with 0
        for i in range(len(nums)):
            p.append(p[-1] + nums[i])  # Store cumulative sum
        
        # Step 2: Iterate through the array and check pivot condition
        for i in range(1, len(p)):
            left_sum = p[i] - nums[i - 1]  # Sum of elements to the left of index i-1
            right_sum = p[-1] - p[i]       # Sum of elements to the right of index i-1
            
            if left_sum == right_sum:
                return i - 1  # Return the pivot index
        
        return -1  # If no pivot index is found

from typing import List

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        # Step 1: Compute prefix sum
        p = [0]  # Prefix sum array initialized with 0
        for i in range(len(nums)):
            p.append(p[-1] + nums[i])  # Store cumulative sum
        
        # Step 2: Iterate through the array and check pivot condition
        for i in range(1, len(p)):
            left_sum = p[i] - nums[i - 1]  # Sum of elements to the left of index i-1
            right_sum = p[-1] - p[i]       # Sum of elements to the right of index i-1
            
            if left_sum == right_sum:
                return i - 1  # Return the pivot index
        
        return -1  # If no pivot index is found

---

▎📝 Explanation of the Code:

1. Building Prefix Sum Array:

   • We initialize p with [0] to store cumulative sums.

   • Iterate through nums, appending the cumulative sum to p.

2. Finding Pivot Index:

   • For each i, compute:

     • Left sum: p[i] - nums[i-1] (sum of elements before index i-1).

     • Right sum: p[-1] - p[i] (sum of elements after index i-1).

   • If both sums are equal, return i-1.

3. Edge Case Handling:

   • If no such index exists, return -1.

---

▎✅ Complexity Analysis:

• Time Complexity: O(N) (single pass for prefix sum + single pass for checking pivot index).

• Space Complexity: O(N) (extra space for prefix sum array).