Given an array of distinct integers arr, where arr is sorted in ascending order, return the smallest index i that satisfies arr[i] == i. If there is no such index, return -1.
Example 1:
Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.
Example 2:
Input: arr = [0,2,5,8,17]
Output: 0
Explanation: arr[0] = 0, thus the output is 0.
Example 3:
Input: arr = [-10,-5,3,4,7,9]
Output: -1
Explanation: There is no such i that arr[i] == i, thus the output is -1.
Constraints:
1 <= arr.length < 104-109 <= arr[i] <= 109Follow up: The O(n) solution is very straightforward. Can we do better?
program main
implicit none
integer, parameter :: n = 6
integer, dimension(n) :: arr
integer :: i
arr = [-10, -5, 0, 3, 7]
write (*, '(I0)') find_smallest_index(arr)
arr = [0, 2, 5, 8, 17]
write (*, '(I0)') find_smallest_index(arr)
arr = [-10, -5, 3, 4, 7, 9]
write (*, '(I0)') find_smallest_index(arr)
contains
function find_smallest_index(arr) result(i)
implicit none
integer, intent(in) :: arr(:)
integer :: i
i = -1
do while (i < size(arr))
if (arr(i+1) == i+1) then
i = i + 1
else
exit
end if
end do
end function find_smallest_index
end program maintemp.f95:8:4:
8 | arr = [-10, -5, 0, 3, 7]
| 1
Error: Different shape for array assignment at (1) on dimension 1 (6 and 5)
temp.f95:11:4:
11 | arr = [0, 2, 5, 8, 17]
| 1
Error: Different shape for array assignment at (1) on dimension 1 (6 and 5)
module smallest_index_i
implicit none
contains
function smallest_index_i(arr) result(i)
integer, intent(in) :: arr(:)
integer :: i, j
! Initialize i to -1
i = -1
! Loop through the array
do j=1,size(arr)
! If the current element is equal to its index, return the index
if (arr(j) == j) then
i = j
exit
end if
end do
end function smallest_index_i
end module
program test_smallest_index_i
use smallest_index_i
implicit none
integer :: arr(5)
! Test case 1:
arr = [-10, -5, 0, 3, 7]
write (*,*) "Smallest index i:", smallest_index_i(arr)
! Test case 2:
arr = [0, 2, 5, 8, 17]
write (*,*) "Smallest index i:", smallest_index_i(arr)
! Test case 3:
arr = [-10, -5, 3, 4, 7, 9]
write (*,*) "Smallest index i:", smallest_index_i(arr)
! Test case 4:
arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
write (*,*) "Smallest index i:", smallest_index_i(arr)
! Test case 5:
arr = [-1, -2, -3, -4, -5, -6, -7, -8, -9]
write (*,*) "Smallest index i:", smallest_index_i(arr)
end program
temp.f95:4:25:
4 | function smallest_index_i(arr) result(i)
| 1
Error: MODULE attribute of ‘smallest_index_i’ conflicts with PROCEDURE attribute at (1)
temp.f95:5:29:
5 | integer, intent(in) :: arr(:)
| 1
Error: Unexpected data declaration statement in CONTAINS section at (1)
temp.f95:6:15:
6 | integer :: i, j
| 1
Error: Unexpected data declaration statement in CONTAINS section at (1)
temp.f95:9:6:
9 | i = -1
| 1
Error: Unexpected assignment statement in CONTAINS section at (1)
temp.f95:12:16:
12 | do j=1,size(arr)
| 1
Error: Unexpected DO statement in CONTAINS section at (1)
temp.f95:14:25:
14 | if (arr(j) == j) then
| 1
Error: Unexpected block IF statement in CONTAINS section at (1)
temp.f95:15:13:
15 | i = j
| 1
Error: Unexpected assignment statement in CONTAINS section at (1)
temp.f95:16:12:
16 | exit
| 1
Error: EXIT statement at (1) is not within a construct
temp.f95:17:7:
17 | end if
| 1
Error: Expecting END MODULE statement at (1)
temp.f95:18:3:
18 | end do
| 1
Error: Expecting END MODULE statement at (1)
temp.f95:20:3:
20 | end function smallest_index_i
| 1
Error: Expecting END MODULE statement at (1)
temp.f95:24:5:
24 | use smallest_index_i
| 1
Fatal Error: Cannot open module file ‘smallest_index_i.mod’ for reading at (1): No such file or directory
compilation terminated.
def fixedPoint(arr: List[int]) -> int:
left, right = 0, len(arr) - 1
while left < right:
middle = left + (right - left) // 2
if arr[middle] < middle:
left = middle + 1
else:
right = middle
return left if arr[left] == left else -1
The algorithm uses binary search to efficiently find the fixed point in the sorted array of distinct integers. Since the array is sorted, when arr[middle] < middle, we can conclude that a fixed point (if exists) must be at middle or at the right side of middle, so we set left to middle + 1. In other cases, when arr[middle] >= middle, we set right to middle. This process continues until left < right is no longer true.
After exiting the loop, we check if arr[left] is equal to left. If yes, we return left as the fixed point index, otherwise we return -1, as no fixed point exists.
The time complexity of the algorithm is O(log n), as we divide the search interval by half at each step.
int fixedPoint(vector<int>& arr) {
int left = 0, right = arr.size() - 1;
while (left < right) {
int middle = left + (right - left) / 2;
if (arr[middle] < middle) {
left = middle + 1;
} else {
right = middle;
}
}
return arr[left] == left ? left : -1;
}
The algorithm uses binary search to efficiently find the fixed point in the sorted array of distinct integers. Since the array is sorted, when arr[middle] < middle, we can conclude that a fixed point (if exists) must be at middle or at the right side of middle, so we set left to middle + 1. In other cases, when arr[middle] >= middle, we set right to middle. This process continues until left < right is no longer true.
After exiting the loop, we check if arr[left] is equal to left. If yes, we return left as the fixed point index, otherwise we return -1, as no fixed point exists.
The time complexity of the algorithm is O(log n), as we divide the search interval by half at each step.