Basic implementation, Greedy
You are given two integers N and K, you have to partition N into K distinct positive integers X1 + X2+ … + XK = N.
You have to find the maximum possible value of the product (x1 2−x1)⋅(x22−x2)⋅…⋅(xK2 −xK) and print it modulo 1e9+7.
with K we can get the minimum sum 1 + 2 + 3 … K = K(K+1) / 2*
here we observed that if N < K(K + 1) /2*, we can’t partition N into K distinct positive integers, so the answer will be -1.
Otherwise we need to find out the valid K distinct elements, for doing this
- first take K elements 1,2,3…K
- now calculate the difference between N and K * (K + 1) / 2 because we have already taken elements from 1 … K so we got the sum K * (K + 1) / 2
d = N - (K * (K + 1) / 2)
now we need this more to get sum equals to N
- now need equal distribution of d among K elements, So
c = d / K
r = d % K (if d is not divisible by K)
- increase all K chosen elements by c and increase last r elements by 1
- we got K elements with sum equals to N
Just calculate the answer of calculated K elements and take it’s modulo 1e9+7.
Time complexity is O(K) per test case.
Editorialist’s solution can be found
Feel free to Share your approach, If it differs. Suggestions are always welcomed.