To make the product of all elements zero, we need at least one element in the array to be zero.

There are three cases to consider:

• If there is already a zero in the array, no operations are needed.
• If there are negative numbers, we can turn one of them into zero, requiring at most |A[i]| operations.
• If all numbers are positive, the minimum number of operations required is to turn the smallest positive number into zero.

n = int(input())
nums = list(map(int, input().split()))

min_operations = float('inf')
zero_found = False

for num in nums:
    if num == 0:
        zero_found = True
        break
    min_operations = min(min_operations, abs(num))

if zero_found:
    print(0)
else:
    print(min_operations)

def solve():
    n  = int(input())
    a = [abs(int(x)) for x in input().split()]
    print(min(a))
    
solve()

To solve this problem efficiently, consider how elements are positioned in the matrix and how to avoid double-counting.

The problem requires us to identify and sum specific elements in an n × n matrix where n is odd. The elements to be considered are:

• Elements of the main diagonal: These are the elements where the row index equals the column index, i.e., (i, i).
• Elements of the secondary diagonal: These are the elements where the sum of the row index and column index equals n − 1, i.e., (i, n − 1 − i).
• Elements of the middle row: This is the row that has exactly ((n − 1) / 2) rows above and below it.
• Elements of the middle column: This is the column that has exactly (n − 1) / 2 columns to the left and right of it.

n = int(input())  
matrix = []  
for _ in range(n):  
    inp = [int(i) for i in input().split()]  
    matrix.append(inp)  

visited = set()  
mid_row = mid_col = n // 2  
ans = 0  

for i in range(n):  
    # Main diagonal  
    if (i, i) not in visited:  
        ans += matrix[i][i]  
        visited.add((i, i))  

    # Secondary diagonal  
    if (i, n - 1 - i) not in visited:  
        ans += matrix[i][n - 1 - i]  
        visited.add((i, n - 1 - i))  

    # Middle row  
    if (mid_row, i) not in visited:  
        ans += matrix[mid_row][i]  
        visited.add((mid_row, i))  

    # Middle column  
    if (i, mid_col) not in visited:  
        ans += matrix[i][mid_col]  
        visited.add((i, mid_col))  

print(ans)

Time Complexity = O(n)

'''
Basic Properties
 <> i == j --> main diagonal
 <> i + j == ( n - 1)  --> secondary diagonal
 <> i == n//2  -->  middle row
 <> j == n//2  --> middle column
'''
def solve():
    matrix = []
    n = int(input())
    for i in range(n):
        row = list(map(int , input().split()))
        matrix.append(row)

    ans = 0
    for i in range(n):
        for j in range(n):
            if i == j or i == n//2  or j == n//2 or i + j == n - 1 :
                ans += matrix[i][j]
             
    print(ans)
                
    


solve()

Time Complexity = O(n * n)

We need to split the string $$$s$$$ into two non-empty parts $$$a$$$ and $$$b$$$ such that the sum of distinct characters in both parts is maximized. The key observation here is that we can efficiently track the distinct characters in both parts as we move through the string. We can solve this problem by iterating over each character of the string and keeping track of two sets:

• One set for characters in the left part (which means for $$$a$$$).
• One set for characters in the right part (which means for $$$b$$$).

• Start by putting all characters in the right part of the string.
• Iterate through each character in the string, shifting one character at a time from the right part to the left part, and updating the distinct character counts for both parts.
• At each step, compute the sum of distinct characters in both parts and keep track of the maximum sum observed.

from collections import Counter

def max_distinct_split(s):
    right_counter = Counter(s)  # Tracks character counts in the right part
    left_counter = Counter()    # Tracks character counts in the left part
    max_distinct_sum = 0        # Stores the maximum sum of distinct characters

    for char in s:
        # Move character from right part to left part
        left_counter[char] += 1
        right_counter[char] -= 1

        # If a character count in the right part becomes zero, remove it
        if right_counter[char] == 0:
            del right_counter[char]

        # Calculate the sum of distinct characters in both parts
        distinct_sum = len(left_counter) + len(right_counter)
        max_distinct_sum = max(max_distinct_sum, distinct_sum)

    return max_distinct_sum


t = int(input())

for _ in range(t):
    n = int(input())
    s = input()
    print(max_distinct_split(s))

To solve this problem, we need to validate whether a given Minesweeper field is consistent with the rules of the game. We are given a grid where each cell can either be empty, contain a digit (from $$$1$$$ to $$$8$$$), or a bomb ($$$'*’$$$). The task is to ensure that for each cell with a digit $$$k$$$, exactly $$$k$$$ neighboring cells contain bombs. For empty cells ($$$'.'$$$), all surrounding cells must be free of bombs. We iterate through the grid, for each non-bomb cell, we count the number of bombs in its $$$8$$$ neighboring cells. If a numbered cell doesn't match the expected bomb count, or if an empty cell has surrounding bombs, we flag the grid as invalid. If the entire grid passes the checks, we output $$$"YES"$$$; otherwise, $$$"NO"$$$.

n, m = map(int, input().split())  # Read dimensions of the grid
grid = []

# Read the grid input
for _ in range(n):
    row = input()
    grid.append(row)

# Directions for 8 neighboring cells (up, down, left, right, and diagonals)
directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

def is_inbound(x, y):
    """Check if the given coordinates are within the grid bounds."""
    return 0 <= x < n and 0 <= y < m

def count_bombs(x, y):
    """Count the number of bombs surrounding a given cell."""
    bomb_count = 0
    for dx, dy in directions:
        ni, nj = x + dx, y + dy
        if is_inbound(ni, nj) and grid[ni][nj] == '*':
            bomb_count += 1
            
    return bomb_count

valid = True  # Flag to track validity of the field

# Iterate through each cell in the grid
for i in range(n):
    for j in range(m):
        if grid[i][j] == '*':
            continue  # Bomb cells are inherently valid
        
        bomb_count = count_bombs(i, j)
        
        if grid[i][j] == '.':  # Empty cell should not have any bombs around it
            if bomb_count > 0:
                valid = False
        else:  # Numbered cell should match the count of surrounding bombs
            if int(grid[i][j]) != bomb_count:
                valid = False

# Print result based on validity
print("YES" if valid else "NO")

Let's rotate the grid by 0∘, 90∘, 180∘, and 270∘, and mark all cells that map to each other under these rotations. For example, for 4×4 and 5×5 grids, the grid must have the following patterns, the same letters denoting equal values:

In general, we can rotate the grid by 0∘, 90∘, 180∘, and 270∘ and see which cells need to have equal values by seeing the positions which each cell maps to.

Now to solve the problem, we consider each equal value (each of the letters a, b, c, ... in the above figures) independently, and consider the minimum number of moves to make them all 0 or all 1. The answer is the total across all values.

The time complexity is O($$$ n^2 $$$). And the space complexity is O($$$ 1 $$$).

Let's consider the upper triangular quarter of the grid. If we are at $$$(i, j)$$$, after rotating it by 0∘, 90∘, 180∘, and 270∘, the bit at this position is replaced by the one at $$$(j, n - i - 1)$$$, $$$(n - i - 1, n - j - 1)$$$, $$$(n - j - 1, i)$$$ respectively. From these four positions we count the numbers of zeros and ones and take the minimum. We sum those minimums for all positions in the upper triangular quarter of the grid.

t = int(input())
for _ in range(t):

    n = int(input())
    
    grid = []
    for i in range(n):
        grid.append(input())
    

    min_ops = 0

    for row in range(n//2):
        for col in range(row, n - row - 1):
            
            zero_one_count = [0, 0]

            zero_one_count[int(grid[row][col])] += 1
            zero_one_count[int(grid[col][n - row - 1])] += 1
            zero_one_count[int(grid[n - row - 1][n - col - 1])] += 1
            zero_one_count[int(grid[n - col - 1][row])] += 1

            min_ops += min(zero_one_count)

    print(min_ops)