Given an integer array arr, return true if there are three consecutive odd numbers in the array. Otherwise, return false.
Example 1:
Input: arr = [2,6,4,1] Output: false Explanation: There are no three consecutive odds.
Example 2:
Input: arr = [1,2,34,3,4,5,7,23,12] Output: true Explanation: [5,7,23] are three consecutive odds.
Constraints:
1 <= arr.length <= 10001 <= arr[i] <= 1000program main
implicit none
integer, parameter :: n = 9
integer :: i, j, k
integer :: arr(n) = [2, 6, 4, 1, 3, 5, 7, 23, 12]
logical :: result
do i = 1, n - 2
do j = i + 1, n - 1
do k = j + 1, n
if (mod(arr(i), 2) /= 0 .and. mod(arr(j), 2) /= 0 .and. &
mod(arr(k), 2) /= 0) then
write (*, '(A, L1)') 'Result: ', (arr(i) == arr(j) + 1 .and. arr(j) == arr(k) + 1)
exit
end if
end do
end do
end do
end program mainResult: F Result: F Result: F Result: F Result: F Result: F
program consecutive_odd
implicit none
integer, parameter :: int64 = selected_int_kind(13)
integer(int64), dimension(:), allocatable :: arr
integer(int64) :: i, n
logical :: result
! read input
read(*,*) n
allocate(arr(n))
do i = 1, n
read(*,*) arr(i)
end do
! solve problem
result = consecutive_odd_sub(arr, n)
! print output
write(*,*) result
contains
function consecutive_odd_sub(arr, n) result(consecutive_odd)
implicit none
integer(int64), dimension(:), intent(in) :: arr
integer(int64), intent(in) :: n
logical :: consecutive_odd
integer(int64) :: i
consecutive_odd = .false.
do i = 1, n - 2
if (mod(arr(i), 2) == 1 .and. mod(arr(i+1), 2) == 1 .and. mod(arr(i+2), 2) == 1) then
consecutive_odd = .true.
exit
end if
end do
end function consecutive_odd_sub
end program consecutive_odd
At line 11 of file temp.f95 (unit = 5, file = 'stdin') Fortran runtime error: End of file Error termination. Backtrace: #0 0x78d112217960 in ??? #1 0x78d1122184d9 in ??? #2 0x78d11246c17b in ??? #3 0x78d112465684 in ??? #4 0x78d1124662aa in ??? #5 0x580b3532b3ca in MAIN__ #6 0x580b3532b698 in main
import heapq
def kthSmallest(mat, k):
m, n = len(mat), len(mat[0])
minHeap = [(mat[0][0], 0, 0)]
visited = [[False for _ in range(n)] for _ in range(m)]
visited[0][0] = True
for _ in range(k):
res, i, j = heapq.heappop(minHeap)
if i < m - 1 and not visited[i+1][j]:
heapq.heappush(minHeap, (res - mat[i][j] + mat[i + 1][j], i + 1, j))
visited[i+1][j] = True
if j < n - 1 and not visited[i][j+1]:
heapq.heappush(minHeap, (res - mat[i][j] + mat[i][j + 1], i, j + 1))
visited[i][j+1] = True
return res
The algorithm uses a min-heap data structure initialized with the smallest element (top-left corner) of the matrix. We maintain a matrix visited of booleans that tells if an element of the matrix is in the heap.
In each iteration, the algorithm pops the smallest element from the min-heap, updates the result, and inserts the elements below and to the right of the matrix, if they have not been visited yet. This process is repeated k times. After the kth iteration, the result holds the sum of the kth smallest array.
The algorithm has a time complexity of O(k * (m + n)), since in the worst case we have to visit all elements of all rows and columns m and n times (when k = m * n).
Note that in JavaScript, we do not use a priority queue implementation. Instead, we add elements to the array and sort the array each time after adding elements. This gives slightly worse performance in practice, but for the given problem size, it should suffice.
#include <vector>
#include <queue>
int kthSmallest(const std::vector<std::vector<int>>& mat, int k) {
int m = mat.size(), n = mat[0].size();
auto comp = [&](const std::vector<int>& a, const std::vector<int>& b) {
return a[0] > b[0];
};
std::priority_queue<std::vector<int>, std::vector<std::vector<int>>, decltype(comp)> minHeap(comp);
minHeap.push({mat[0][0], 0, 0});
std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));
visited[0][0] = true;
int res;
while (k--) {
auto cur = minHeap.top(); minHeap.pop();
res = cur[0];
int i = cur[1], j = cur[2];
if (i < m - 1 && !visited[i+1][j]) {
minHeap.push({res - mat[i][j] + mat[i + 1][j], i + 1, j});
visited[i+1][j] = true;
}
if (j < n - 1 && !visited[i][j+1]) {
minHeap.push({res - mat[i][j] + mat[i][j + 1], i, j + 1});
visited[i][j+1] = true;
}
}
return res;
}
The algorithm uses a min-heap data structure initialized with the smallest element (top-left corner) of the matrix. We maintain a matrix visited of booleans that tells if an element of the matrix is in the heap.
In each iteration, the algorithm pops the smallest element from the min-heap, updates the result, and inserts the elements below and to the right of the matrix, if they have not been visited yet. This process is repeated k times. After the kth iteration, the result holds the sum of the kth smallest array.
The algorithm has a time complexity of O(k * (m + n)), since in the worst case we have to visit all elements of all rows and columns m and n times (when k = m * n).
Note that in JavaScript, we do not use a priority queue implementation. Instead, we add elements to the array and sort the array each time after adding elements. This gives slightly worse performance in practice, but for the given problem size, it should suffice.