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"

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"

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

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")

Input: nums = [13, 25, 83, 77]
Output: [1, 3, 2, 5, 8, 3, 7, 7]
Explanation: 
- The separation of 13 is [1, 3].
- The separation of 25 is [2, 5].
- The separation of 83 is [8, 3].
- The separation of 77 is [7, 7].
answer = [1, 3, 2, 5, 8, 3, 7, 7].

Input: nums = [7, 1, 3, 9]
Output: [7, 1, 3, 9]
Explanation: The separation of each integer in nums is itself.
answer = [7, 1, 3, 9].

class Solution:
    def separateDigits(self, nums: List[int]) -> List[int]:
        result = []
        for num in nums:
            digits = list(str(num))  # Convert number to string and split into characters
            result.extend(int(digit) for digit in digits)  # Convert characters back to integers and add to result
        return result

class Solution:
    def separateDigits(self, nums: List[int]) -> List[int]:
        return list(map(int,list(''.join(map(str,nums)))))

class Solution:
    def separateDigits(self, nums: List[int]) -> List[int]:
        result = []
        
        for num in nums:
            digits = []
            while num > 0:
                digits.append(num % 10)  # Extract the last digit
                num //= 10  # Remove the last digit
            
            result.extend(digits[::-1])  # Reverse to maintain order
        
        return result

class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        return ["FizzBuzz" if i % 3 == 0 and i % 5 == 0 else
                "Fizz" if i % 3 == 0 else
                "Buzz" if i % 5 == 0 else str(i)
                for i in range(1, n + 1)]

class Solution:
    def passThePillow(self, n: int, time: int) -> int:
        cycle = (time % (2 * (n - 1)))
        return n - abs(n - 1 - cycle)

class Solution:
    def finalValueAfterOperations(self, operations: List[str]) -> int:
        return sum(1 if '+' in op else -1 for op in operations)

class Solution:
    def transformedArray(self, arr: List[int]) -> List[int]:
        while True:
            new_arr = arr[:]
            changed = False
            for i in range(1, len(arr) - 1):
                new_val = (arr[i-1] + arr[i+1]) // 2
                if new_val != arr[i]:
                    new_arr[i] = new_val
                    changed = True
            if not changed:
                return arr
            arr = new_arr

class Solution:
    def getLucky(self, s: str, k: int) -> int:
        num = ''.join(str(ord(c) - ord('a') + 1) for c in s)
        for _ in range(k):
            num = str(sum(int(d) for d in num))
        return int(num)

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        return len(s.strip().split()[-1])

🟢 Time Complexity: O(n)  
🟢 Space Complexity: O(1)  

---

▎2️⃣ Find Three Consecutive Integers That Sum to a Given Number (Problem Link)

Problem: Find three consecutive integers whose sum equals num. If not possible, return an empty array.  

Python Solution:  

class Solution:
    def sumOfThree(self, num: int) -> List[int]:
        if num % 3 != 0:
            return []
        x = num // 3
        return [x - 1, x, x + 1]

🟢 Time Complexity: O(1)  
🟢 Space Complexity: O(1)  

---

▎3️⃣ Rotate String (Problem Link)

Problem: Given two strings s and goal, check if s can become goal after some number of left rotations.  

Python Solution:  

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        return len(s) == len(goal) and goal in (s + s)

🟢 Time Complexity: O(n)  
🟢 Space Complexity: O(n)  

---

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False
        return goal in (s + s)

class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        # Check for empty matrix
        if not matrix or not matrix[0]:
            return []
        
        m, n = len(matrix), len(matrix[0])
        result = []
        row, col = 0, 0
        # direction = 1 means moving up-right; direction = -1 means moving down-left.
        direction = 1
        
        while len(result) < m * n:
            result.append(matrix[row][col])
            
            if direction == 1:  # Moving up-right.
                # If we're at the last column, we can only go down.
                if col == n - 1:
                    row += 1
                    direction = -1
                # If we're at the top row, we can only go right.
                elif row == 0:
                    col += 1
                    direction = -1
                else:
                    row -= 1
                    col += 1
            else:  # direction == -1, Moving down-left.
                # If we're at the bottom row, we can only go right.
                if row == m - 1:
                    col += 1
                    direction = 1
                # If we're at the first column, we can only go down.
                elif col == 0:
                    row += 1
                    direction = 1
                else:
                    row += 1
                    col -= 1
        
        return result