Medium - Find the Minimum Possible Sum of a Beautiful Array

https://leetcode.com/problems/find-the-minimum-possible-sum-of-a-beautiful-array/description/

문제 설명

You are given positive integers n and target.

An array nums is beautiful if it meets the following conditions:

• nums.length == n.
• nums consists of pairwise distinct positive integers.
• There doesn't exist two distinct indices, i and j, in the range [0, n - 1], such that nums[i] + nums[j] == target.

Return the minimum possible sum that a beautiful array could have modulo 10 ** 9 + 7.

 

Constraints:

• 1 <= n <= 10 ** 9
• 1 <= target <= 10 ** 9

예시

Example 1:

Input: n = 2, target = 3
Output: 4
Explanation: We can see that nums = [1,3] is beautiful.
- The array nums has length n = 2.
- The array nums consists of pairwise distinct positive integers.
- There doesn't exist two distinct indices, i and j, with nums[i] + nums[j] == 3.
It can be proven that 4 is the minimum possible sum that a beautiful array could have.

Example 2:

Input: n = 3, target = 3
Output: 8
Explanation: We can see that nums = [1,3,4] is beautiful.
- The array nums has length n = 3.
- The array nums consists of pairwise distinct positive integers.
- There doesn't exist two distinct indices, i and j, with nums[i] + nums[j] == 3.
It can be proven that 8 is the minimum possible sum that a beautiful array could have.

Example 3:

Input: n = 1, target = 1
Output: 1
Explanation: We can see, that nums = [1] is beautiful.

풀이

class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int:
        mod_val = 10 ** 9 + 7
        # ans = 0
        # i = 1
        # while i <= int(target/2) and i <=n:
        #     ans += i
        #     i += 1

        # j = target
        # while i <= n:
        #     ans += j
        #     j += 1
        #     i += 1

        # return ans % mod_val

        left_num = min(int(target / 2), n)
        right_num = n - left_num

        left_val = int(left_num * (left_num + 1) / 2)
        right_val = int((2 * target + right_num - 1) / 2 * right_num) if right_num > 0 else 0

        return (left_val + right_val) % mod_val

두 자연수를 더해서 target이 되는 값은 [n, target - n]이다. 따라서 target보다 작은 수의 갯수는 min(n, int(target / 2))가 되고, 여기까지의 SUM은 [1, min(n, int(target / 2))]의 합이 된다. (가능한 가장 작은 합이므로 1부터 시작한다.)

위에서 구한 target보다 작은 수 (== left_num)가 n보다 작다면, [target, target + (n - left_num) - 1] 역시 정답에 더한다. (== right_val)

left_val과 right_val을 합한 값의 mod 10 ^ 9 + 7이 정답이 된다.

 

위에서 말한 수식을 풀어쓴 게 코멘트아웃한 정답이다.

이 답도 시간복잡도 O(n) = n, 공간복잡도 O(n) = 1로 충분히 좋은 정답인 것 같은데, TC 중에 굉장히 높은 값을 주고 Time Limit Exceeded 억까하는 케이스가 있어서 위처럼 O(1)의 수식으로 풀어야 통과했다.