Given an integer n, return true if n has exactly three positive divisors. Otherwise, return false.
An integer m is a divisor of n if there exists an integer k such that n = k * m.
Example 1:
Input: n = 2 Output: false Explantion: 2 has only two divisors: 1 and 2.
Example 2:
Input: n = 4 Output: true Explantion: 4 has three divisors: 1, 2, and 4.
Constraints:
1 <= n <= 104program main
implicit none
integer :: n
logical :: result
! Example 1
n = 2
result = hasThreePositiveDivisors(n)
print '(L1)', result
! Example 2
n = 4
result = hasThreePositiveDivisors(n)
print '(L1)', result
contains
function hasThreePositiveDivisors(n) result(result)
implicit none
integer, value :: n
logical :: result
integer :: i
result = .false.
do i = 1, n - 1
if (mod(n, i) == 0) then
result = result .or. hasThreePositiveDivisors(i)
if (result) exit
end if
end do
end function hasThreePositiveDivisors
end program maintemp.f95:28:36:
28 | result = result .or. hasThreePositiveDivisors(i)
| 1
Error: Function ‘hasthreepositivedivisors’ at (1) cannot be called recursively, as it is not RECURSIVE
module example
implicit none
contains
function has_three_divisors(n) result(has_divisors)
integer, intent(in) :: n
logical :: has_divisors
integer :: i, divisors
divisors = 0
do i = 1, n
if (n / i == n) then
divisors = divisors + 1
end if
end do
has_divisors = (divisors == 3)
end function has_three_divisors
end module example
program test
use example
implicit none
integer :: n
n = 2
write (*,*) has_three_divisors(n)
n = 4
write (*,*) has_three_divisors(n)
n = 6
write (*,*) has_three_divisors(n)
end program test
F F F
def minSideJumps(obstacles):
n = len(obstacles)
dp = [[n] * 3 for _ in range(n)]
dp[0][1] = 0
dp[0][0] = dp[0][2] = 1
for i in range(1, n):
if obstacles[i] != 1:
dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + 1, dp[i - 1][2] + 1)
if obstacles[i] != 2:
dp[i][1] = min(dp[i - 1][1], dp[i - 1][0] + 1, dp[i - 1][2] + 1)
if obstacles[i] != 3:
dp[i][2] = min(dp[i - 1][2], dp[i - 1][0] + 1, dp[i - 1][1] + 1)
return min(dp[-1])
We maintain a dynamic programming table (dp) with dimensions n x 3 where each row i represents the current point and each column j with [0, 2] represents the lanes. The value stored in dp[i][j] is the minimum number of side jumps needed to reach the lane j at point i. We initially set all values in the table to n (the maximum possible number of side jumps), and set the values for the initial point (dp[0]) accordingly.
We then iterate through each point from 1 to n-1, checking if there is no obstacle for each lane. If there is no obstacle for lane j, we update the values in the table dp[i][j] by taking the minimum value between the previous value in the same lane or one plus the previous value in the other two lanes.
After filling the table, we return the minimum value in the last row, which represents the minimum number of side jumps needed to reach any lane at point n.
int minSideJumps(vector<int>& obstacles) {
vector<vector<int>> dp(obstacles.size(), vector<int>(3, obstacles.size()));
dp[0][1] = 0;
dp[0][0] = 1;
dp[0][2] = 1;
for (size_t i = 1; i < obstacles.size(); ++i) {
if (obstacles[i] != 1) dp[i][0] = min(dp[i-1][0], min(dp[i-1][1] + 1, dp[i-1][2] + 1));
if (obstacles[i] != 2) dp[i][1] = min(dp[i-1][1], min(dp[i-1][0] + 1, dp[i-1][2] + 1));
if (obstacles[i] != 3) dp[i][2] = min(dp[i-1][2], min(dp[i-1][0] + 1, dp[i-1][1] + 1));
}
return min(dp.back()[0], min(dp.back()[1], dp.back()[2]));
}
We maintain a dynamic programming table (dp) with dimensions n x 3 where each row i represents the current point and each column j with [0, 2] represents the lanes. The value stored in dp[i][j] is the minimum number of side jumps needed to reach the lane j at point i. We initially set all values in the table to n (the maximum possible number of side jumps), and set the values for the initial point (dp[0]) accordingly.
We then iterate through each point from 1 to n-1, checking if there is no obstacle for each lane. If there is no obstacle for lane j, we update the values in the table dp[i][j] by taking the minimum value between the previous value in the same lane or one plus the previous value in the other two lanes.
After filling the table, we return the minimum value in the last row, which represents the minimum number of side jumps needed to reach any lane at point n.