Maximum Split of Positive Even Integers

You are given an integer finalSum. Split it into a sum of a maximum number of unique positive even integers.

  • For example, given finalSum = 12, the following splits are valid (unique positive even integers summing up to finalSum): (12), (2 + 10), (2 + 4 + 6), and (4 + 8). Among them, (2 + 4 + 6) contains the maximum number of integers. Note that finalSum cannot be split into (2 + 2 + 4 + 4) as all the numbers should be unique.

Return a list of integers that represent a valid split containing a maximum number of integers. If no valid split exists for finalSum, return an empty list. You may return the integers in any order.

 

Example 1:

Input: finalSum = 12
Output: [2,4,6]
Explanation: The following are valid splits: (12), (2 + 10), (2 + 4 + 6), and (4 + 8).
(2 + 4 + 6) has the maximum number of integers, which is 3. Thus, we return [2,4,6].
Note that [2,6,4], [6,2,4], etc. are also accepted.

Example 2:

Input: finalSum = 7
Output: []
Explanation: There are no valid splits for the given finalSum.
Thus, we return an empty array.

Example 3:

Input: finalSum = 28
Output: [6,8,2,12]
Explanation: The following are valid splits: (2 + 26), (6 + 8 + 2 + 12), and (4 + 24). 
(6 + 8 + 2 + 12) has the maximum number of integers, which is 4. Thus, we return [6,8,2,12].
Note that [10,2,4,12], [6,2,4,16], etc. are also accepted.

 

Constraints:

  • 1 <= finalSum <= 1010
SOLUTION:
class Solution:
    def maximumEvenSplit(self, finalSum: int) -> List[int]:
        res = []
        if finalSum & 1:
            return res
        i = 1
        while i * (i + 1) <= finalSum:
            res.append(2 * i)
            i += 1
        if i * (i + 1) > finalSum:
            res.pop()
            res.append(finalSum - (i - 1) * (i - 2))
        return res

Comments

Post a Comment

Popular posts from this blog

Lazy Deletion in Heap: A Wrapper for Python heapq

Lazy Deletion in Heap: A Wrapper for Python heapq Lazy Deletion in Heap: A Wrapper for Python heapq In many programming scenarios, we often encounter situations where we need to maintain a heap data structure and perform operations such as insertion, deletion, and retrieval of the minimum element efficiently. Python provides a built-in module called heapq that offers heap operations. However, the standard heapq module does not provide direct support for lazy deletion, which can be useful in certain cases. In this article, we will explore a wrapper class, Heap , that extends the functionality of the Python heapq library to support lazy deletion in a heap. The Heap Class The Heap class is a wrapper that encapsulates the heapq module to enable lazy deletion in a heap. Let's go through its main methods and their functionalities: __init__(self) : Initializes the Heap instance by creating an empty heap and a defaultdict to track the deleted elements ...
Read more

Sliding Window GCD

Sliding Window GCD Sliding Window GCD Problem Description You are given an array of integers nums of length N . There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return an array of length N - k + 1 representing the GCD of each subarray of length k from left to right. Solution Approach The solution to this problem involves implementing a special queue data structure using two stacks. This special queue allows the push , pop , and GCD operations in O(1) amortized time complexity. The implementation of this queue is based on the combination of two existing techniques: implementing a queue using stacks and implementing a stack that stores GCD values. By using this special queue, we can efficiently calculate the GCD for each sliding window in O(N) time complexity. This technique is useful to understand the impl...
Read more

Degree of an Array

Given a non-empty array of non-negative integers nums , the degree of this array is defined as the maximum frequency of any one of its elements. Your task is to find the smallest possible length of a (contiguous) subarray of nums , that has the same degree as nums .   Example 1: Input: nums = [1,2,2,3,1] Output: 2 Explanation: The input array has a degree of 2 because both elements 1 and 2 appear twice. Of the subarrays that have the same degree: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] The shortest length is 2. So return 2. Example 2: Input: nums = [1,2,2,3,1,4,2] Output: 6 Explanation: The degree is 3 because the element 2 is repeated 3 times. So [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.   Constraints: nums.length will be between 1 and 50,000. nums[i] will be an integer between 0 and 49,999. SOLUTION: from collections import defaultdict class Solution : def findShortestSubArr...
Read more