famish99
BAN USERThe trick to this problem is recognizing that for a possible solution, given a list of consecutive numbers, the mean must equal the median.
Such as in 24 = 7 + 8 + 9, since the three values average out to 8, if you do a search where 24 / 3 = 8, you know you need 3 values where the mean and median is 8, so 7, 8 and 9.
The obvious solution would be to stop dividing when you reach the sum value, but to save operations, you can also stop dividing when the half of the divider (i.e. half the numbers needed for the list) is greater than the quotient. (Basically if you need 7 numbers to the left of the median but the result of the median is 6, you can't make the list because it requires all natural numbers)
The real meat of this problem is just coming up with the list, so I'll avoid all the tedious bits about getting output from the console.
Code is in python 2, but would work for python 3 if you change the print statement, the division types are correct for both syntaxes
def print_list(sum):
num_list = get_list(sum)
if num_list is None:
print "IMPOSSIBLE"
return
print "%d = %s " % (sum, ' + '.join([str(i) for i in num_list]))
def get_list(sum):
divisor = 2
while (divisor / 2.0 < 1.0 * sum / divisor):
return_list = [i for i in range(
int((1.0 * sum / divisor) - (divisor / 2.0)) + 1,
int((1.0 * sum / divisor) + (divisor / 2.0)) + 1)] # generate list of consecutive numbers
list_length = len(return_list)
median = sum // divisor # using floor division, not a comment
if list_length % 2 == 0 and return_list[(list_length >> 1) - 1] == median:
return return_list
elif list_length % 2 == 1 and return_list[list_length >> 1)] == median:
return return_list
divisor += 1
return None
I should have said it wouldn't work for numbers where large number of consecutive numbers were required to reach the sum. While in practice that may not be required but if the problem asked you to find instances where the list needed to be 10k large you could get into issues with relying on recursion and the hard-coded shift array. If there is an iterative solution available, why not take it?
- famish99 November 14, 2015