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)

For a specific C, what happens to those elements that appear in our array less than C times?

What about the elements that appear C or more times?

For a given integer $$$C$$$, all elements in the array that appear less than $$$C$$$ times should be deleted to make the array beautiful because we can’t increase their frequency as we are only allowed to delete elements and not add. For elements that appear $$$C$$$ or more times, $$$count_x$$$ — $$$C$$$ elements should be deleted for every integer x in the given array where $$$count_x$$$ is the number of times $$$x$$$ appears in the given array.

Let's have a dictionary $$$dict$$$ to count the frequency of each number in the given array. Let $$$\mathbf{min}_{count}$$$, $$$\mathbf{max}_{count}$$$ be the minimum and maximum frequencies(values) we have in $$$dict$$$. To find the optimal answer $$$\mathbf{min}_{count}$$$ <= $$$C$$$ <= $$$\mathbf{max}_{count}$$$ should be satisfied. If $$$C$$$ is outside that range, we will have to delete more elements than necessary and we can't find the optimal answer that way.

• Let $$$removed$$$ be our variable to count the number of elements we will remove to make the given array beautiful. We have at most $$$n$$$ different values for $$$C$$$ in that range.
• For every $$$C$$$ we can iterate over $$$dict$$$ and we will add $$$dict[x]$$$ to removed if $$$dict[x]$$$ < $$$C$$$ and $$$C$$$ - $$$dict[x]$$$ otherwise. This would take $$$O(n^2)$$$ time.

But note that if there is no such number y such that $$$dict[y]$$$ = $$$C$$$, then such a value of $$$C$$$ will not give the minimum answer (because we have removed unnecessary elements). So if we consider only the frequencies that exist in $$$dict$$$ we can find our answer in $$$O(\sqrt{n} . n)$$$ time.

• $$$\text{Time Complexity: } O(\sqrt{n} . n)$$$
• $$$\text{Space Complexity: } O(n)$$$

from collections import Counter
t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))

    count = Counter(arr)

    options = set(count.values())
    min_deletions = float('inf')
    
    #c is always in range 1 to n
    for c in range(1, n + 1):
        if c not in options:
            continue

        deletions = 0
        for num in count:
            if count[num] < c:
                deletions += count[num]
            else:
                deletions += count[num] - c
        
        min_deletions = min(min_deletions, deletions)
    
    print(min_deletions)

What if we sort each number based on their frequency ?

Let’s have a new array called $$$arr$$$. For every $$$key, value$$$ pair we have in our $$$dict$$$, we add $$$value$$$ (frequencies) to $$$arr$$$ and sort it. Then we can iterate over this array and for every unique frequency we get in our iteration we can easily count how many elements we need to remove to make the given array beautiful as follows: $$$removed$$$ = $$$n - (len(arr) - i) * arr[i]$$$.

Here $$$C = arr[i]$$$. If we have already calculated our answer for this particular $$$C$$$ (that is, $$$i > 0$$$ and $$$arr[i] == arr[i - 1]$$$ is $$$True$$$), we move on to the next iteration. Otherwise we are sure that there are $$$len(arr) - i$$$ unique elements that exist $$$arr[i]$$$ or more times. Since we only want each of them to appear exactly $$$arr[i]$$$ times, we will end up with $$$arr[i] * (len(arr) - i)$$$ elements in our array. That’s why $$$removed = n - (len(arr) - i) * arr[i]$$$ is $$$True$$$

• $$$\text{Time Complexity: } O(nlogn)$$$
• $$$\text{Space Complexity: } O(n)$$$

from collections import Counter
t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))

    count = Counter(arr)

    values = list(count.values())
    values.sort()

    min_deletions = float('inf')
    
    for i in range(len(values)):
        # you can add the following if condition to only count deletions for
        # unique values of c = arr[i] but it's not mandatory. 
        # if i > 0 and values[i] == values[i - 1]:
        #    continue

        deletions = n - (len(values) - i) * values[i]
        min_deletions = min(min_deletions, deletions)
    
    print(min_deletions)

This problem can be solved using a dictionary to track the count of each number in the array. By iterating through the array and incrementing the count of each number in the dictionary, we calculate the current count (current_count) for each number. Additionally, we utilize another dictionary (appearance_dict) to monitor the total size of the numbers for each frequency count (calculated as frequency_count * frequency = the total size). This calculation allows us to understand the array's total size if the frequency is set as C.

After traversing through the array, we determine the maximum value in the appearance_dict dictionary. This value signifies the maximum size capable of accommodating numbers. The key retrieved from the dictionary indicates the maximum frequency for each unique number, necessary to make the array beautiful. Our goal is to ensure each number appears either zero or C times. Hence, we must eliminate all elements except those appearing C times. Consequently, the number of elements to remove equals the total number of elements minus the maximum value found in the appearance_dict dictionary.

• $$$\text{Time Complexity: } O(nl)$$$
• $$$\text{Space Complexity: } O(n)$$$

from collections import defaultdict

t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))

    count = defaultdict(int)
    appearance_dict = defaultdict(int)

    for num in nums:
        count[num] += 1
        current_count = count[num]
        appearance_dict[current_count] += 1

    max_appearance = 0

    for key , value in appearance_dict.items():
        max_appearance = max(key * value , max_appearance)

    print(n - max_appearance)