Ah ha! Your example output showed the result 6 8. Using 1-based indexes (common in certain programming challenges), server_lst had in that sub-list the values [6, 7, 8] whose sum is 21, which is close to the target value of 23. I was looking at total < c_power, and thought I was looking at a bug since it would be ignoring a sub-list that totalled exactly 23 as too large.
Your "very simple input" is actually confusing, since server powers and indices are not distinct values. Similarly, the sorted order gives no clear indication of whether 0-based or 1-based indices are returned.
The lack of good comments, an inaccessible problem statement, and confusing code made it hard to tell what the code was intended to do, which made "reviewing the code" a difficult and error-prone task.
Now that I understand what is going on, let's do both: review the code and optimize it.
Code Review
Naming
Your functions and variables are a mix of understandable names (num_of_cases, and num_of_servers) and completely opaque names that don't convey any meaning (execute, and mf).
Globals
Global variables have their place. This isn't it.
The function servers returns nothing, but calls out total and j as global variables it will be reading and writing. It turns out that it is actually modifying server_total and server_index as well.
More likely that not, the total and j variables need not have been global, and could simply have been initialized to zero at the start of the function. Except that if the loop inside servers reaches the end of the loop without exceeding c_power, then j and total are not cleared, and the next call to servers will continue where they left off. Was this intentional? Some kind of wrap-around? It doesn't seem likely, since the starting point k on the next call is not the start of the list, so odds are this is actually a bug.
Unnecessary parameters and variables
def execute(server_lst, k):
for i in range(len(server_lst)):
k = i
servers(server_lst, k)
What is the point of k? Both of them.
The execute function requires a k argument, but whatever value is given will be ignored, overwritten by k = i before it is ever used.
Inside the for loop, the value of i is stored in k. Then, neither I nor k is modified inside the body of the loop, nor used outside of the loop. i == k remains true as long as both variables are in scope. Which begs the question of: why use k instead of i?
Don't define functions inside of loops
This one can really result in strange behaviour.
for _ in range(2):
try:
f()
except NameError:
print("f() didn't exist")
def f():
print("Hello world")
Output:
f() didn't exist
Hello world
Write for testing
If you structured your code as a function which solved the problem, and used a main guard to run the code when submitted to the programming challenge site ...
def find_minimum_power_sublist(server_powers, required_power):
# ... implementation omitted ...
return start, end
def main():
num_cases = int(input())
for case in range(1, num_cases+1):
num_servers, required_power = map(int, input().split())
server_powers = list(map(int, input().split()))
start, end = find_minimum_power_sublist(server_powers, required_power)
print('Case #{}:'.format(case), start, end)
if __name__ == '__main__':
main()
... then you could write a test program which runs sample cases, something like:
from solution import find_minimum_power_sublist
def test(test_name, powers, required_power, expected):
actual = find_minimum_power_sublist(powers, required_power)
if expected == actual:
print(test_name, "passed.")
else:
print(test_name, "failed! Expected:", expected, actual)
def run_tests():
test("1-10", [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 23, (6, 8))
# ... more test cases here ...
if __name__ == '__main__':
run_tests()
There are test frameworks which make testing easier. Look into pytest, unittest, and doctest. Those will get you started, but there are many others you can try.
Optimization
Partial Sums
Whenever you see a problem where you are adding up a sequence of numbers, starting and ending at different points, you should stop and ask if there is a better way.
In your example, you have the numbers 1 2 3 4 5 6 7 8 9 10, and you first start with 1, then 1+2, then 1+2+3, and so on, until you arrive at the total of 1+2+3+4+5+6+7 or 28. Then you reset and start 2, 2+3, 2+3+4, and so on until you reach 2+3+4+5+6+7 or 27. Then you reset and start at 3 and compute 3+4, 3+4+5, 3+4+5+6, 3+4+5+6+7 or 25. Then you reset and start 4, 4+5, 4+5+6, 4+5+6+7, 4+5+6+7+8 or 30.
How many times have you added 4 and 5 together? Or phrased a better way, how many times have you added 5 to a previous sum that included the four term? Only four times. Not a lot. But this is an example with only 10 servers. You could have one hundred thousand servers and a fairly high power threshold to exceed. You could be repeatedly add a specific server value to a previous total thousands of times, and since you can have thousands of individual server values, you've got an \$O(N^2)\$ algorithm.
Instead, consider a running total of the values: 1 3 6 10 15 21 28 36 45 55. We've added the server value to the previous total exactly once. From that list, you can get the sum of any sublist of servers. For instance the sum of server values from index 6 to index 8 would be the sum of server values up to index 8, 45, less the sum of server values up to index 5, 21. 45-21=24. After processing the list of N servers, doing a total of N additions, you can get the sum of any sublist with at most one subtraction!
As exciting as this sounds, this hasn't actually improved anything. Using the same steps above, algorithm would still start with 1-0, 3-0, 6-0, 10-0, 15-0, 21-0, 28-0, then reset to 3-1, 6-1, 10-1, 15-1, 21-1, 28-1, and then reset to 6-3, up to 28-3, then reset to 10-6 up to 36-6, and so on. Instead of doing one addition per loop step, we're doing one subtraction per loop step.
Why reset to the beginning?
After adding the server power values until you exceeded the requirement, why reset the sequence and walk up to the threshold again? Why not simply advance the starting point of the sublist until the threshold is no longer reached?
- We move the end-point forward until the difference is greater than or equal to the requirement:
1-0, 3-0, 6-0, 10-0, 15-0, 21-0, 28-0.
- Then we walk the start-point forward until we dip below the requirement:
28-1, 28-3, 28-6.
- Then we return to walking the end-point forward until the requirement is met again:
36-6.
- Then we return to walking the start-point forward:
36-10, 36-15.
- Walk end-point forward:
45-15.
- Walk start-point forward:
45-21, 45-28.
- Walk end-point forward:
55-28.
- Walk start-point forward:
55-36
- Walk end-point forward: end-of-list
More concisely,
- While the total power requirement is not satisfied,
- walk the end-point forward
- While the total power requirement is satisfied,
- If total power is smaller than the smallest found so far:
- update the smallest found so far, and memorize the start and end points.
- walk the start-point forward
Note we're only walking the start-point and end-point forward through the list once. This is \$O(N)\$.
Running totals
You don't have to precompute and store the running totals. You could just keep two running totals as you move the starting point and ending point forward.
You don't even need two totals. Just add or subtract from a single running total. Or consider the total a surplus, and initialize it with the negative of the power requirement. When surplus >= 0, the power requirement is satisfied; when surplus < 0, the power requirement is not satisfied.
