Max Elements Sum upto Target | Coding Challenge

This coding question was asked of me in the Cisco Technical interview.

Problem statement:

Find the maximum elements in a given array that would sum up to a given target.

Constraints:

The maximum number of elements in the array is 25.

Input:

1. ⁠The first line specifies the number of elements in the array plus the target.
2. The second line specified the target
3. Subsequent lines contain the elements of array (Integers)

Output:

• Integer specifying the maximum number of elements that sum up to a given target.
• Return 0 if there is no match.

Example 1

Input:

5
10
2
3
5
5

Output:

3

Explanation:

Following are the possible combinations

• 2, 3, 5 (Total elements: 3)
• 5, 5 (Total elements: 2)

The solution is option 1 as it has maximum elements (i.e. 3 elements – 2, 3 and 5

Example 2

Input:

4
5
3
3
3

Output:

0

Explanation:

Elements 3, 3, and 3 don’t sum up to 5 in any combination.

Hence, the output is 0.

Python Solution

def find_max_elements(array):

    if len(array)>25:
        return 0

    target_sum = array[0]
    
    nums = array[1:]
    
    if target_sum==sum(nums):
        return len(nums)
    
    nums.sort()

    max_out = 0
    
    first_index = 0
    while first_index < len(nums):
        cur_out = 1
        cur_sum = nums[first_index]
        if cur_sum==target_sum:
            max_out = max(max_out, cur_out)
            break
        index=first_index+1
        while index < len(nums):
            cur_sum += nums[index]
            cur_out += 1
            if cur_sum > target_sum:
                break
            if cur_sum == target_sum:
                max_out = max(max_out, cur_out)
                break
            index+=1
        first_index+=1
    return max_out

print(find_max_elements([10, 2, 3, 5, 5]))

Output:

3

The code is self-explanatory. If you understand the logic you can implement it in any programming language you choose.

With this solution, I’m able to crack 10 out of 12 test cases. Two test cases were still failing. If you have better solution comment below.

All the best!

Aniruddha Chaudhari

I am a Python enthusiast who loves Linux and Vim. I hold a Master of Computer Science degree from NIT Trichy and have 10 years of experience in the IT industry, focusing on the Software Development Lifecycle from Requirements Gathering, Design, Development to Deployment. I have worked at IBM, Ericsson, and NetApp, and I share my knowledge on CSEstack.org.