Left as an Exercise.
Left as an Exercise.
Implementation: The product of several integers is equal to 1 if and only if each of these numbers is 1 or −1, and there must be an even number of −1 (else the product would give us a negative number).
Let's say there is an element x whose value is neither 1 nor -1 inside our final list. Let's also assume p is the product of all the elements other than our x. Since the product of all the elements should be 1, x * p = 1. We have three choices for x.
1. x == 0, p = 1/0 would be undefined.
2. x > 1, 0 < p = 1/x < 1, which is not integer.
3. x < 1, -1 < p = 1/x< 0, which is also not integer.
By definition, the product of integers (p for our case) should be integers. Therefore, none of the above three choices are possible.
By now, we know we will only have 1 and -1 in our list. So, What happens if we have odd number of -1s? They would make the whole product negative. So make sure you have even number of -1s.
Let's be greedy to minimize our cost. Would it be good/optimal to change a positive number to -1? No, because 1 is closer to all positive numbers. By the same logic, it is good to shift all negative numbers to -1. Therefore, We will have to reduce every positive a[i] at least to one, and we have to spend at least a[i] - 1 coin on this (decrement a[i] until it reaches 1). Similarly, we will have to increase every negative a[i] at least to −1, for this we will spend at least −1−a[i] coins. Note that we haven't touched the zeros yet.
Let's move to the second criteria (having even -1s). If we, currently, have odd -1s, we have two options, either to change one -1 to 1 (which would cost us 1 - (-1) = 2 or change one zero to -1 (which would cost us 0 -(-1) = 1). The later option is optimal. Therefore, whenever we have zeros in our list, change one of them to -1 and the others to 1. However, if there are no zeros, we would be left with only the first option with a cost of 2.
TIME: O(N)
n = int(input())
a = list(map(int, input().split()))
coins = pos = neg = zero = 0
for x in a:
if x == 0:
zero += 1
coins += 1
elif x > 0:
coins += x - 1
pos += 1
else:
coins += -1 - x
neg += 1
if neg % 2 == 1 and zero == 0:
coins += 2
print(coins)
Sorting: All you need is to swap the current minimum with the ith element each time (Selection Sort). Implement selection sort while keeping track of the swaps you make. For each index, you will be doing at max 1 swap. Therefore, the number of swaps never exceeds n.
Time: O(N^2)
n = int(input())
a = list(map(int, input().split()))
swaps = []
for i in range(n):
mn_index = i
for j in range(i + 1, n):
if a[j] < a[mn_index]:
mn_index = j
swaps.append((i, mn_index))
a[mn_index], a[i] = a[i], a[mn_index]
print(len(swaps))
for swap in swaps:
print(*swap)
Two Pointers: The constraint -seats has to be on the same row or column- simplifies the problem. Let's brute force and find the number of possible ways for each row and column. We can find out how many consecutive empty positions in every row and column separately and add them together to form the final answer. We can use two pointers to keep track of the left most open and right most open positions.
If the length of consecutive empty positions is larger than k, then we can add length−k+1 to the final answer.
But, be careful. When k=1, the algorithm shown above gives twice the correct value. Can you see why?
TIME: O(NM)
n, m, k= map(int,input().split())
matrix = [input() for _ in range(n)]
ways = 0
# count adjacent horizontal seats
for i in range(n):
count = 0
for j in range(m):
if matrix[i][j] == '*':
ways += max(0, count - (k - 1))
count = 0
else:
count += 1
ways += max(0, count - (k - 1))
# count adjacent vertical seats
for j in range(m):
count = 0
for i in range(n):
if matrix[i][j] == '*':
ways += max(0, count - (k - 1))
count = 0
else:
count += 1
ways += max(0, count - (k - 1))
if k == 1:
ways //= 2
print(ways)
n, m, k= map(int,input().split())
matrix = [input() for _ in range(n)]
ways = 0
# count adjacent horizontal seats
for row in range(n):
left = 0
for right in range(m):
if matrix[row][right] == '*':
left = right + 1
elif right - left + 1 >= k:
ways += 1
# count adjacent vertical seats
for col in range(m):
left = 0
for right in range(n):
if matrix[right][col] == '*':
left = right + 1
elif right - left + 1 >= k:
ways += 1
if k == 1:
ways //= 2
print(ways)
Comments (0)
