Fortran
Algorithm is as follows:
- Check if the sum of the array is less than
S
- Check if any of the elements of the array equals
S
- Sort array
- Slice linear elements of array & check if sum of slice is
S
- Sum elements by jumping
i
spaces
I have omitted the module quicksort
but it does exactly what it sounds like it does. It passed all the test cases above, but it does fail on the array 0,-1,3,5,7
when asked for 11 (requires cells 1,4,5 (0,3,4 for those stuck on 0-indexes) which can't be done for slicing--I am working on fixing this)
program rand_array_sum
use quicksort
implicit none
integer, dimension(:), allocatable :: array
integer :: n, s
print *,"Enter number of cells in array"
read(*,*) n; allocate(array(n))
print *,"Enter comma-separated integers in array:"
read(*,*) array
print *,"What is the sum you want?"
read(*,*) s
if(s==0) then
print *,1
stop
endif
if(sum(array)< s) then
print *,0
stop
endif
if(any(array==s)) then
print *,1
stop
endif
call sort(array)
print *,"Sorted array:",array
call sum_array(n,array,s)
contains
subroutine sum_array(n,a,s)
integer, intent(in) :: n, a(n), s
integer :: i, j, b
! linear slices
do i=1,n
do j=1,i
!print '("i=",i0," j=",i0," b=",i0)',i,j,abs(i-j)
b=abs(i-j)
if(sum(array(j:n-b))==s) then
print *,1
return
endif
enddo
print *,""
enddo
! jumping slices
do i=2,n
do j=1,n-i+1
if(sum(array(j:n:i))==s) then
print *,1
return
endif
enddo
enddo
! if all as failed, then it cannot be done
print *,0
end subroutine sum_array
end program rand_array_sum