Given a positive integer n, find the pivot integer x such that:
1 and x inclusively equals the sum of all elements between x and n inclusively.Return the pivot integer x. If no such integer exists, return -1. It is guaranteed that there will be at most one pivot index for the given input.
Example 1:
Input: n = 8 Output: 6 Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21.
Example 2:
Input: n = 1 Output: 1 Explanation: 1 is the pivot integer since: 1 = 1.
Example 3:
Input: n = 4 Output: -1 Explanation: It can be proved that no such integer exist.
Constraints:
1 <= n <= 1000program main
implicit none
integer :: n, x
n = 8
call solve(n, x)
print '(I0)', x
n = 1
call solve(n, x)
print '(I0)', x
n = 4
call solve(n, x)
print '(I0)', x
contains
subroutine solve(n, x)
implicit none
integer, intent(in) :: n
integer, intent(out) :: x
integer :: i, sum1, sum2
sum1 = 0
do i = 1, x
sum1 = sum1 + i
end do
sum2 = 0
do i = x+1, n
sum2 = sum2 + i
end do
if (sum1 == sum2) then
x = x
else
x = -1
end if
end subroutine solve
end program main-1 -1 -1
program pivot_integer
implicit none
integer :: n, x, i, sum_left, sum_right
read(*,*) n
sum_left = 0
sum_right = 0
do i = 1, n
sum_left = sum_left + i
end do
do i = n, 1, -1
sum_right = sum_right + i
if (sum_left == sum_right) then
x = i
exit
end if
end do
if (x == 0) then
write(*,*) -1
else
write(*,*) x
end if
end program pivot_integer
At line 6 of file temp.f95 (unit = 5, file = 'stdin') Fortran runtime error: End of file Error termination. Backtrace: #0 0x7b226198e960 in ??? #1 0x7b226198f4d9 in ??? #2 0x7b2261be317b in ??? #3 0x7b2261bdc684 in ??? #4 0x7b2261bdd2aa in ??? #5 0x572268d18209 in MAIN__ #6 0x572268d1838d in main
def find_pivot(n: int) -> int:
total = n * (n + 1) // 2
left_sum = 0
for x in range(1, n + 1):
left_sum += x
if 2 * left_sum == total:
return x
return -1
The algorithm iterates through all the integers between 1 and n (inclusive), calculating the left_sum as it goes. On each iteration, it checks if the left_sum * 2 equals the total sum (calculated as n * (n + 1) / 2). If it does, the algorithm returns the current integer as the pivot integer. If the loop ends without finding a pivot integer, it returns -1.
int findPivot(int n) {
int sum = n * (n + 1) / 2;
int left_sum = 0;
for (int x = 1; x <= n; ++x) {
left_sum += x;
if (2 * left_sum == sum) {
return x;
}
}
return -1;
}
The algorithm iterates through all the integers between 1 and n (inclusive), calculating the left_sum as it goes. On each iteration, it checks if the left_sum * 2 equals the total sum (calculated as n * (n + 1) / 2). If it does, the algorithm returns the current integer as the pivot integer. If the loop ends without finding a pivot integer, it returns -1.