Contiguous subarray of floating numbers sums to integer algorithm

Question

Suppose we have an array A of size n, there are n unsorted floating point numbers. We want to find a contiguous subarray B such that B sums to an integer. Suppose we can use floor function at cost of O(1). Note that we need to return B if such B exists. My idea:

rsum = running sum of A(i.e. rsum[i]=A[1]+A[2]+...+A[i])
for i from 1 to n:
   for j from i to n:
      e = rsum[j]-rsum[i]+A[i]
      if e==floor(e)
         return A[i....j]
return "no such subarray"

This is an O(n^2) algorithm, is there a way to do that in o(n^2)?

Answer 1

If we ignore floating point calculation errors, then we can put fractional parts of running sums into a map and check whether the same fraction exists twice - (close to) O(n) approach.

Considering precision issues, we can sort fractions (or put them into sorted container like RB tree) and get the smallest difference - O(nlogn) approach