Python: Output all ranges that sum up to target sum

Question

Question:

Given K that consists of non-zero, non-negative integers 1 to K, output all the ranges/intervals whose sum is equal to K.

For example, if K is equal to 6, then the output should be [[1,3], [6,6]]. For [1,3], 1+2+3 = 6 and for [6,6], 6 = 6.

My Solution

Here is my solution below, but the time complexity I think is O(N2). Is there a more efficient way to do this?

def targetSum(k):
  nums = list(range(1,k+1))
  res = []
  for end in range(len(nums)):
    start = 0
    while start <= end:
      sumhere = sum(nums[start:end+1])
      if sumhere == k:
        res.append([nums[start], nums[end]])
      start+=1
  return res

targetSum(6)

Answer 1

You can solve this problem in O(sqrt(K)) time using a bit of math.

Range sum is sum of arithmetic progression with difference 1, so we can write formula

K = n/2 * (2*a + n - 1) or
2 * K = n * (2*a + n - 1) 

where n is range size, a is starting value

So we walk through all possible factorizations of 2*K into two divisors 2*K = p * q , and solve simple system

n = p
2*a + n - 1 = q

or

2*a + p - 1 = q
a  = (q + 1 - p) / 2

Note that solution exists for divisors of distinct oddity/evenness/parity (what term is better here?) (otherwise a is not integer), and q must be larger than p (to get positive a) - this fact allows to stop loop earlier.

Example for K=6:

2K = 12
1 * 12 :  n = 1, a = 6   (range 6..6)
2 * 6:   no solution (both even) 
3 * 4:    n = 3, a = 1  (range 1..3)

Simple implementation (for very large values it is a bit slower (twice) than @hilberts_drinking_problem implementation)

def findranges(k):
    n = 1
    kk = 2 * k
    res = []
    while n * n < kk:
        if kk % n == 0:
            q = kk // n
            if (q ^ n) & 1: //compare parity using the least significant bit
                a = (q + 1 - n) // 2
                res.append([a, a + n - 1])
        n += 1
    return res

print(findranges(60))

  

Answer 2

You can do it in O(K) using sliding window concept or two pointers approach you can say.

At sumhere = sum(nums[start:end+1]) step, you calculate sum repeatedly which is causing you O(K^2). Instead keep moving end to the right and keep adding it to the sum. If sum equals K, add to result. If sum > K, start moving start to the right and keep reducing it from the sum while sum > K. If sum equals K, add to result. Repeat this till you process all numbers in the range.

May be or may not be some math trick could help here. I'll let you know if I'm able to come up with even better approach.