Daily Coding Challenge #62

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.

/*
LeetCode - Reformat Date

Given a date string in the form Day Month Year, where:

Day is in the set {"1st", "2nd", "3rd", "4th", ..., "30th", "31st"}.
Month is in the set {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"}.
Year is in the range [1900, 2100].
Convert the date string to the format YYYY-MM-DD, where:

YYYY denotes the 4 digit year.
MM denotes the 2 digit month.
DD denotes the 2 digit day.

Example 1:

Input: date = "20th Oct 2052"
Output: "2052-10-20"
Example 2:

Input: date = "6th Jun 1933"
Output: "1933-06-06"
Example 3:

Input: date = "26th May 1960"
Output: "1960-05-26"

Constraints:

The given dates are guaranteed to be valid, so no error handling is necessary.
*/

class Solution {
public:
string reformatDate(string date) {
stringstream ss(date);
string s;
vector<string> v;
while(ss>>s) v.push_back(s);
string day="";
// extract the day
for(int i=0;i<v[0].size();i++){
if(isdigit(v[0][i])){
day+=v[0][i];
}
}
// e.g. 6 -> 06
if(day.size()==1) day="0"+day;
// extract the month
vector<string> month = {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};
int i=0;
while(v[1]!=month[i]) i++;
string m=to_string(i+1);
if(m.size()==1) m="0"+m;
return v[2] + "-" + m + "-" + day;
}
};


/*
LeetCode - Range Sum of Sorted Subarray Sums

Given the array nums consisting of n positive integers. You computed the sum of all non-empty continous subarrays from the array and then sort them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.

Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10^9 + 7.

Example 1:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13.
Example 2:

Input: nums = [1,2,3,4], n = 4, left = 3, right = 4
Output: 6
Explanation: The given array is the same as example 1. We have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.
Example 3:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 10
Output: 50

Constraints:

1 <= nums.length <= 10^3
nums.length == n
1 <= nums[i] <= 100
1 <= left <= right <= n * (n + 1) / 2
*/

class Solution {
public:
int mod=1e9+7;
int rangeSum(vector<int>& nums, int n, int left, int right) {
vector<int> v;
// build the subarray sum
for(int i=0;i<n;i++){
for(int j=i, sum=0;j<n;j++){
sum+=nums[j];
v.push_back(sum);
}
}
// sort it
sort(v.begin(),v.end());
// left-1 and right-1 because the v starts at index 0
left--; right--;
int ans=0;
for(int i=left;i<=right;i++){
// take mod for each addition
ans=ans+v[i]%mod;
}
return ans;
}
};


/*
LeetCode - Minimum Difference Between Largest and Smallest Value in Three Moves

Given an array nums, you are allowed to choose one element of nums and change it by any value in one move.

Return the minimum difference between the largest and smallest value of nums after perfoming at most 3 moves.

Example 1:

Input: nums = [5,3,2,4]
Output: 0
Explanation: Change the array [5,3,2,4] to [2,2,2,2].
The difference between the maximum and minimum is 2-2 = 0.
Example 2:

Input: nums = [1,5,0,10,14]
Output: 1
Explanation: Change the array [1,5,0,10,14] to [1,1,0,1,1].
The difference between the maximum and minimum is 1-0 = 1.
Example 3:

Input: nums = [6,6,0,1,1,4,6]
Output: 2
Example 4:

Input: nums = [1,5,6,14,15]
Output: 1

Constraints:

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
*/

class Solution {
public:
int minDifference(vector<int>& nums) {
int n = nums.size();
// we can change at most 3 moves
// if n<=3, we can change all elements to the same value
if(n<=3) return 0;
// sort the nums
sort(nums.begin(),nums.end());
// there are 4 possible solutions
return min({
// change the first 3
nums[n-1]-nums[3],
// change the first 2, and the last 1
nums[n-2]-nums[2],
// change the first 1, and the last 2
nums[n-3]-nums[1],
// change the last 3
nums[n-4]-nums[0]
});
}
};



/*
LeetCode - Stone Game IV

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are n stones in a pile.  On each player's turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer n. Return True if and only if Alice wins the game otherwise return False, assuming both players play optimally.

Example 1:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.
Example 2:

Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).
Example 3:

Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).
Example 4:

Input: n = 7
Output: false
Explanation: Alice can't win the game if Bob plays optimally.
If Alice starts removing 4 stones, Bob will remove 1 stone then Alice should remove only 1 stone and finally Bob removes the last one (7 -> 3 -> 2 -> 1 -> 0).
If Alice starts removing 1 stone, Bob will remove 4 stones then Alice only can remove 1 stone and finally Bob removes the last one (7 -> 6 -> 2 -> 1 -> 0).
Example 5:

Input: n = 17
Output: false
Explanation: Alice can't win the game if Bob plays optimally.

Constraints:

1 <= n <= 10^5
*/

class Solution {
public:
bool winnerSquareGame(int n) {
// dp[i] means the result for n=i
// if dp[i-k*k] is false, we can make the other to lose
// so dp[i]=true
vector<int> dp(n+1,0);
for(int i=1;i<=n;i++){
for(int k=1;k*k<=i;k++){
dp[i]|=!dp[i-k*k];
}
}
return dp[n];
}
};


The source code is available in corresponding repo below. Star and watch for timely updates!

wingkwong / atcoder

Posted on by:

Wing-Kam

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.