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)?

MBo · Accepted Answer · 2019-10-22 02:48:20Z

2

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

edited Oct 22, 2019 at 2:48

answered Oct 21, 2019 at 17:45

MBo

80.7k5 gold badges61 silver badges99 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Eric Postpischil Over a year ago

A map is not properly O(1) insertion time, and so is not overall O(n) for inserting all the elements and checking for a duplicate.

MBo Over a year ago

Yes, I know, but O(1) is typical time and it is usually used for rough estimation

Collectives™ on Stack Overflow

Contiguous subarray of floating numbers sums to integer algorithm

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related