Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
You are given a positive integer num
. You may swap any two digits of num
that have the same parity (i.e. both odd digits or both even digits).
Return the largest possible value of num
after any number of swaps.
Example 1:
Input: num = 1234
Output: 3412
Explanation: Swap the digit 3 with the digit 1, this results in the number 3214.
Swap the digit 2 with the digit 4, this results in the number 3412.
Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number.
Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.
Example 2:
Input: num = 65875
Output: 87655
Explanation: Swap the digit 8 with the digit 6, this results in the number 85675.
Swap the first digit 5 with the digit 7, this results in the number 87655.
Note that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.
Constraints:
1 <= num <= 109
class Solution {
public:
int largestInteger(int num) {
priority_queue<int> p; // priority queue to store odd digits in descending order
priority_queue<int> q; // priority queue to store even digits in descending order
string nums=to_string(num); // converting num to a string for easy access of the digits
int n=nums.size(); // n stores the number of digits in num
for(int i=0;i<n;i++){
int digit=nums[i]-'0';
if((digit)%2) // if digit is odd, push it into priority queue p
p.push(digit);
else
q.push(digit); // if digit is even, push it into priority queue q
}
int answer=0;
for(int i=0; i<n; i++){
answer=answer*10;
if((nums[i]-'0')%2) // if the digit is odd, add the largest odd digit of p into the answer
{answer+=p.top();p.pop();}
else
{answer+=q.top();q.pop();} // if the digit is even, add the largest even digit of q into the answer
}
return answer;
}
};
public int largestInteger(int n){
char[] a = String.valueOf(n).toCharArray();
for(int i = 0; i < a.length; i++)
for(int j = i + 1; j < a.length; j++)
if(a[j] > a[i] && (a[j] - a[i]) % 2 == 0){
char t = a[i];
a[i] = a[j];
a[j] = t;
}
return Integer.parseInt(new String(a));
}
class Solution:
def largestInteger(self, num: int):
n = len(str(num))
arr = [int(i) for i in str(num)]
odd, even = [], []
for i in arr:
if i % 2 == 0:
even.append(i)
else:
odd.append(i)
odd.sort()
even.sort()
res = 0
for i in range(n):
if arr[i] % 2 == 0:
res = res*10 + even.pop()
else:
res = res*10 + odd.pop()
return res
class Solution:
def largestInteger(self, num: int):
n = len(str(num))
arr = [int(i) for i in str(num)]
odd, even = [], []
for i in arr:
if i % 2 == 0:
even.append(i)
else:
odd.append(i)
odd.sort()
even.sort()
res = 0
for i in range(n):
if arr[i] % 2 == 0:
res = res*10 + even.pop()
else:
res = res*10 + odd.pop()
return res
You are given a 0-indexed string expression
of the form "<num1>+<num2>"
where <num1>
and <num2>
represent positive integers.
Add a pair of parentheses to expression
such that after the addition of parentheses, expression
is a valid mathematical expression and evaluates to the smallest possible value. The left parenthesis must be added to the left of '+'
and the right parenthesis must be added to the right of '+'
.
Return expression
after adding a pair of parentheses such that expression
evaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.
The input has been generated such that the original value of expression
, and the value of expression
after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.
Example 1:
Input: expression = "247+38"
Output: "2(47+38)"
Explanation: The expression evaluates to 2 * (47 + 38) = 2 * 85 = 170.
Note that "2(4)7+38" is invalid because the right parenthesis must be to the right of the '+'.
It can be shown that 170 is the smallest possible value.
Example 2:
Input: expression = "12+34"
Output: "1(2+3)4"
Explanation: The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.
Example 3:
Input: expression = "999+999"
Output: "(999+999)"
Explanation: The expression evaluates to 999 + 999 = 1998.
Constraints:
3 <= expression.length <= 10
expression
consists of digits from '1'
to '9'
and '+'
.expression
starts and ends with digits.expression
contains exactly one '+'
.expression
, and the value of expression
after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.public String minimizeResult(String str) {
int n=str.length();
int idx=0;
while(idx<n && str.charAt(idx)!='+') idx++;
idx++;
int ans=1000000000;
String res="";
for(int i=0;i<idx-1;i++){
for(int j=idx;j<n;j++){
StringBuilder sb=new StringBuilder(str);
sb.insert(j+1,')');
sb.insert(i,'(');
int a=0,b=0,c=0,d=0,k=0;
for(;sb.charAt(k)!='(';k++){
a=a*10+(sb.charAt(k)-'0');
}
k++;
for(;sb.charAt(k)!='+';k++){
b=b*10+(sb.charAt(k)-'0');
}
k++;
for(;sb.charAt(k)!=')';k++){
c=c*10+(sb.charAt(k)-'0');
}
k++;
for(;k<sb.length();k++){
d=d*10+(sb.charAt(k)-'0');
}
b=b+c;
if(a==0) a=1;
if(d==0) d=1;
int abc=a*b*d;
if(abc<ans){
res=sb.toString();
ans=abc;
}
}
}
return res;
}
string minimizeResult(string str) {
int n=str.length();
int idx=0;
while(idx<n && str[idx]!='+') idx++;
idx++;
int ans=1000000000;
string res="";
for(int i=0;i<idx-1;i++){
for(int j=idx;j<n;j++){
string sb=str.substr(0,i) + "(" + str.substr(i,j+1-i) + ")" +str.substr(j+1,n);
int a=0,b=0,c=0,d=0,k=0;
for(;sb[k]!='(';k++){
a=a*10+(sb[k]-'0');
}
k++;
for(;sb[k]!='+';k++){
b=b*10+(sb[k]-'0');
}
k++;
for(;sb[k]!=')';k++){
c=c*10+(sb[k]-'0');
}
k++;
for(;k<sb.length();k++){
d=d*10+(sb[k]-'0');
}
b=b+c;
if(a==0) a=1;
if(d==0) d=1;
int abc=a*b*d;
if(abc<ans){
res=sb;
ans=abc;
}
}
}
return res;
}
class Solution:
def minimizeResult(self, expression: str) -> str:
plus_index, n, ans = expression.find('+'), len(expression), [float(inf),expression]
def evaluate(exps: str):
return eval(exps.replace('(','*(').replace(')', ')*').lstrip('*').rstrip('*'))
for l in range(plus_index):
for r in range(plus_index+1, n):
exps = f'{expression[:l]}({expression[l:plus_index]}+{expression[plus_index+1:r+1]}){expression[r+1:n]}'
res = evaluate(exps)
if ans[0] > res:
ans[0], ans[1] = res, exps
return ans[1]
/**
* @param {string} expression
* @return {string}
*/
var minimizeResult = function(expression) {
const [left, right] = expression.split("+");
let res = [`(${expression})`, +left + +right];
for(let i = 0; i < left.length; i++) {
const i1 = left.slice(0, i) || 1;
const i2 = left.slice(i);
for(let j = 1; j <= right.length; j++) {
const j1 = right.slice(0, j);
const j2 = right.slice(j) || 1;
const tempTotal = i1*(+i2 + +j1)*j2;
if(res[1] > tempTotal ) {
res[0] = `${left.slice(0, i)}(${i2}+${j1})${right.slice(j)}`;
res[1] = tempTotal
}
}
}
return res[0]
};
You are given an array of non-negative integers nums
and an integer k
. In one operation, you may choose any element from nums
and increment it by 1
.
Return the maximum product of nums
after at most k
operations. Since the answer may be very large, return it modulo 109 + 7
. Note that you should maximize the product before taking the modulo.
Example 1:
Input: nums = [0,4], k = 5
Output: 20
Explanation: Increment the first number 5 times.
Now nums = [5, 4], with a product of 5 * 4 = 20.
It can be shown that 20 is maximum product possible, so we return 20.
Note that there may be other ways to increment nums to have the maximum product.
Example 2:
Input: nums = [6,3,3,2], k = 2
Output: 216
Explanation: Increment the second number 1 time and increment the fourth number 1 time.
Now nums = [6, 4, 3, 3], with a product of 6 * 4 * 3 * 3 = 216.
It can be shown that 216 is maximum product possible, so we return 216.
Note that there may be other ways to increment nums to have the maximum product.
Constraints:
1 <= nums.length, k <= 105
0 <= nums[i] <= 106
```
int maximumProduct(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> pq;
long long ans=1, MOD = 1e9+7;
if(nums.size()==1){
ans=(k+nums[0])%MOD;
return ans;
}
for(auto ele:nums) pq.push(ele);
while(k) {
int x = pq.top(); pq.pop();
int y=pq.top(); pq.pop();
int diff=min(k,y-x+1);
x+=diff;
k-=diff;
pq.push(x);
pq.push(y);
}
while(!pq.empty()) {
int x = pq.top(); pq.pop();
ans = (ans*x)%MOD;
}
return ans;
}
```
public int maximumProduct(int[] nums, int k) {
int n=nums.length;
long mod=1000000007;
if(n==1){
long ans=(nums[0]+k)%mod;
return (int)ans;
}
PriorityQueue<Long> pq=new PriorityQueue<>();
for(int a:nums){
pq.add((long)a);
}
while(k>0){
long num1=pq.remove();
long num2=pq.remove();
long diff=Math.min(k,(num2-num1)+1);
num1+=diff;
k-=diff;
pq.add(num1);
pq.add(num2);
}
long ans=1;
while(!pq.isEmpty()){
ans=(ans*pq.remove())%mod;
}
return (int)ans;
}
import heapq
class Solution:
def maximumProduct(self, nums, k: int) -> int:
# creating a heap
heap = []
for i in nums:
heapq.heappush (heap,i)
# basic idea here is keep on incrementing smallest number, then only multiplication of that number will be greater
# so basically till I have operations left I will increment my smallest number
while k :
current = heapq.heappop(heap)
heapq.heappush(heap, current+1)
k-=1
result =1
# Just Multiply all the numbers in heap and return the value
while len(heap)>0:
x= heapq.heappop(heap)
result =(result*x )% (10**9+7)
return result
Alice is a caretaker of n
gardens and she wants to plant flowers to maximize the total beauty of all her gardens.
You are given a 0-indexed integer array flowers
of size n
, where flowers[i]
is the number of flowers already planted in the ith
garden. Flowers that are already planted cannot be removed. You are then given another integer newFlowers
, which is the maximum number of flowers that Alice can additionally plant. You are also given the integers target
, full
, and partial
.
A garden is considered complete if it has at least target
flowers. The total beauty of the gardens is then determined as the sum of the following:
full
.partial
. If there are no incomplete gardens, then this value will be 0
.Return the maximum total beauty that Alice can obtain after planting at most newFlowers
flowers.
Example 1:
Input: flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1
Output: 14
Explanation: Alice can plant
- 2 flowers in the 0th garden
- 3 flowers in the 1st garden
- 1 flower in the 2nd garden
- 1 flower in the 3rd garden
The gardens will then be [3,6,2,2]. She planted a total of 2 + 3 + 1 + 1 = 7 flowers.
There is 1 garden that is complete.
The minimum number of flowers in the incomplete gardens is 2.
Thus, the total beauty is 1 * 12 + 2 * 1 = 12 + 2 = 14.
No other way of planting flowers can obtain a total beauty higher than 14.
Example 2:
Input: flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6
Output: 30
Explanation: Alice can plant
- 3 flowers in the 0th garden
- 0 flowers in the 1st garden
- 0 flowers in the 2nd garden
- 2 flowers in the 3rd garden
The gardens will then be [5,4,5,5]. She planted a total of 3 + 0 + 0 + 2 = 5 flowers.
There are 3 gardens that are complete.
The minimum number of flowers in the incomplete gardens is 4.
Thus, the total beauty is 3 * 2 + 4 * 6 = 6 + 24 = 30.
No other way of planting flowers can obtain a total beauty higher than 30.
Note that Alice could make all the gardens complete but in this case, she would obtain a lower total beauty.
Constraints:
1 <= flowers.length <= 105
1 <= flowers[i], target <= 105
1 <= newFlowers <= 1010
1 <= full, partial <= 105
class Solution:
def maximumBeauty(self, A: List[int], new: int, t: int, full: int, part: int) -> int:
A = [min(t, a) for a in A]
A.sort()
# Two edge cases
if min(A) == t: return full * len(A)
if new >= t * len(A) - sum(A):
return max(full*len(A), full*(len(A)-1) + part*(t-1))
# Build the array `cost`.
cost = [0]
for i in range(1, len(A)):
pre = cost[-1]
cost.append(pre + i * (A[i] - A[i - 1]))
# Since there might be some gardens having `target` flowers already, we will skip them.
j = len(A) - 1
while A[j] == t:
j -= 1
# Start the iteration
ans = 0
while new >= 0:
# idx stands for the first `j` gardens, notice a edge case might happen.
idx = min(j, bisect_right(cost, new) - 1)
# bar is the current minimum flower in the incomplete garden
bar = A[idx] + (new - cost[idx]) // (idx + 1)
ans = max(ans, bar * part + full *(len(A) - j - 1))
# Now we would like to complete garden j, thus deduct the cost for garden j
# from new and move on to the previous(next) incomplete garden!
new -= (t - A[j])
j -= 1
return ans
long long maximumBeauty(vector<int>& fl, long long newFlowers, int target, int full, int partial) {
sort(begin(fl), end(fl), greater<int>());
long long p1 = 0, sum = 0, res = 0, sz = fl.size();
for (; p1 < sz; ++p1) {
if (target - fl[p1] > newFlowers)
break;
newFlowers -= max(0, target - fl[p1]);
}
if (p1 == sz)
return max(sz * full, (sz - 1) * full + (fl.back() < target ? (long long)(target - 1) * partial : full));
for (long long minF = fl.back(), p2 = fl.size() - 1; minF < target; ) {
while (p2 >= p1 && fl[p2] <= minF)
sum += fl[p2--];
int needed = (sz - p2 - 1) * minF - sum;
if (needed > newFlowers) {
if (--p1 < 0)
break;
newFlowers += max(0, target - fl[p1]);
}
else {
res = max(p1 * full + minF * partial, res);
++minF;
}
}
return res;
}
class Solution {
public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
int n = flowers.length;
long[] prefix = new long[n + 1];
Arrays.sort(flowers);
for (int i = 0; i < n; ++i) prefix[i + 1] = prefix[i] + Math.min(flowers[i], target);
long res = 0;
for (int c = 0, i = n - 1; c <= n; ++c) {
long remain = prefix[n] - prefix[n - c] + newFlowers - c * (long) target, min = 0;
if (0 > remain) break;
i = Math.min(i, n - c - 1);
while (0 <= i && (target <= flowers[i] || flowers[i] * (long) (i + 1) - prefix[i + 1] > remain)) i--;
if (0 <= i) {
long dif = flowers[i] * (long) (i + 1) - prefix[i + 1];
min = Math.min(target - 1, flowers[i] + (remain - dif) / (i + 1));
if (i + 1 < n - c) min = Math.min(min, flowers[i + 1]);
}
res = Math.max(res, c * (long) full + min * (long) partial);
}
return res;
}
}
In our experience, we suggest you solve this Weekly Contest 288 Leetcode Solutions and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Weekly Contest 288 Leetcode Solutions
I hope this Weekly Contest 288 Leetcode Solutions would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More Coding Solutions >>