Skip to content

Instantly share code, notes, and snippets.

@lebedov
Created July 25, 2018 14:09
Show Gist options
  • Save lebedov/3c02232a8d009de9a91eddd49e6a60dc to your computer and use it in GitHub Desktop.
Save lebedov/3c02232a8d009de9a91eddd49e6a60dc to your computer and use it in GitHub Desktop.
Given a list of integers, determine the index of the least upper bound of some value that is in the cumulative sum array of the list.
import bisect
import itertools
def find_lub_cumsum_index(a, x):
a_cumsum = list(itertools.accumulate(a))
i = bisect.bisect_right(a_cumsum, x)
if i != len(a):
return i
raise ValueError
if __name__ == '__main__':
import unittest
class test_find_lub_cumsum_index(unittest.TestCase):
@classmethod
def setUpClass(cls):
cls.arr = [30, 15, 20]
def test_within_bounds(self):
self.assertEqual(find_lub_cumsum_index(self.arr, 20), 0)
self.assertEqual(find_lub_cumsum_index(self.arr, 40), 1)
self.assertEqual(find_lub_cumsum_index(self.arr, 45), 2)
def test_above_bounds(self):
with self.assertRaises(ValueError):
find_lub_cumsum_index(self.arr, 65)
unittest.main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment