Given an array of integers arr, return true if we can partition the array into three non-empty parts with equal sums.
Formally, we can partition the array if we can find indexes i + 1 < j with (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])
Example 1:
Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1] Output: true Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
Example 2:
Input: arr = [0,2,1,-6,6,7,9,-1,2,0,1] Output: false
Example 3:
Input: arr = [3,3,6,5,-2,2,5,1,-9,4] Output: true Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
Constraints:
3 <= arr.length <= 5 * 104-104 <= arr[i] <= 104program main
implicit none
integer, parameter :: n = 10
integer, dimension(n) :: arr
logical :: result
! Example 1
arr = [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1]
write(*,*) 'Example 1'
write(*,*) 'Input: ', arr
result = canPartition(arr)
write(*,*) 'Output: ', result
write(*,*) ''
! Example 2
arr = [0, 2, 1, -6, 6, 7, 9, -1, 2, 0, 1]
write(*,*) 'Example 2'
write(*,*) 'Input: ', arr
result = canPartition(arr)
write(*,*) 'Output: ', result
write(*,*) ''
! Example 3
arr = [3, 3, 6, 5, -2, 2, 5, 1, -9, 4]
write(*,*) 'Example 3'
write(*,*) 'Input: ', arr
result = canPartition(arr)
write(*,*) 'Output: ', result
write(*,*) ''
contains
function canPartition(arr) result(result)
implicit none
integer, dimension(:), intent(in) :: arr
logical :: result
integer :: i, j
do i = 1, size(arr)-2
do j = i+1, size(arr)-1
if (sum(arr(1:i)) == sum(arr(i+1:j)) .and. &
sum(arr(j+1:size(arr))) == sum(arr(1:j))) then
result = .true.
exit
end if
end do
if (result) exit
end do
end function canPartition
end program maintemp.f95:9:4:
9 | arr = [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1]
| 1
Error: Different shape for array assignment at (1) on dimension 1 (10 and 11)
temp.f95:17:4:
17 | arr = [0, 2, 1, -6, 6, 7, 9, -1, 2, 0, 1]
| 1
Error: Different shape for array assignment at (1) on dimension 1 (10 and 11)
```
program partitionEqualSum
implicit none
integer, parameter :: INT_MAX = huge(1)
integer, parameter :: INT_MIN = -huge(1)
integer, dimension(:), allocatable :: arr
integer :: n, i, j, sum1, sum2, sum3
read *, n
allocate(arr(n))
read *, arr
! Initialize sums
sum1 = 0
sum2 = 0
sum3 = 0
! Calculate sums
do i = 1, n
sum1 = sum1 + arr(i)
end do
! Find mid index
i = 1
j = n
do while (i < j)
if (sum1 == sum2 .and. sum2 == sum3) then
exit
end if
if (sum1 < sum2) then
sum1 = sum1 + arr(i)
i = i + 1
else
sum2 = sum2 + arr(j)
j = j - 1
end if
sum3 = sum3 + arr(j)
end do
! Check if sums are equal
if (sum1 == sum2 .and. sum2 == sum3) then
write (*, '(A)') "True"
else
write (*, '(A)') "False"
end if
deallocate(arr)
end program partitionEqualSum
```
temp.f95:1:2:
1 | ```
| 1
Error: Invalid character in name at (1)
temp.f95:53:2:
53 | ```
| 1
Error: Invalid character in name at (1)
def fib(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
The algorithm iterates from 2 to n using a loop that calculates the current Fibonacci number by adding the two previous ones. It uses three variables a, b, and c, representing the two previous Fibonacci numbers and the current one, respectively. At each iteration, the algorithm calculates the current Fibonacci number, updates a and b, and repeats. This minimizes the extra space needed and avoids recursion, resulting in an efficient O(n) time complexity solution.
int fib(int n) {
if (n <= 1)
return n;
int a = 0, b = 1, c;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
The algorithm iterates from 2 to n using a loop that calculates the current Fibonacci number by adding the two previous ones. It uses three variables a, b, and c, representing the two previous Fibonacci numbers and the current one, respectively. At each iteration, the algorithm calculates the current Fibonacci number, updates a and b, and repeats. This minimizes the extra space needed and avoids recursion, resulting in an efficient O(n) time complexity solution.