# Daily Coding Challenge #77

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 - Count Odd Numbers in an Interval Range

Given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive).

Example 1:

Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].
Example 2:

Input: low = 8, high = 10
Output: 1
Explanation: The odd numbers between 8 and 10 are .

Constraints:

0 <= low <= high <= 10^9
*/

class Solution {
public:
int countOdds(int low, int high) {
int sum=0;
if(low%2==0) low++;
for(int i=low;i<=high;i+=2) sum++;
return sum;
}
};

class Solution2 {
public:
int countOdds(int low, int high) {
return (high+1)/2-low/2;
}
};


/*
LeetCode - Number of Sub-arrays With Odd Sum

Given an array of integers arr. Return the number of sub-arrays with odd sum.

As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: arr = [1,3,5]
Output: 4
Explanation: All sub-arrays are [,[1,3],[1,3,5],,[3,5],]
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.
Example 2:

Input: arr = [2,4,6]
Output: 0
Explanation: All sub-arrays are [,[2,4],[2,4,6],,[4,6],]
All sub-arrays sum are [2,6,12,4,10,6].
All sub-arrays have even sum and the answer is 0.
Example 3:

Input: arr = [1,2,3,4,5,6,7]
Output: 16
Example 4:

Input: arr = [100,100,99,99]
Output: 4
Example 5:

Input: arr = 
Output: 1

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 100
*/

class Solution {
public:
int numOfSubarrays(vector<int>& arr) {
// odd+odd=even
// odd+even=odd
// even+even=even
// v: even prefix sum
// v: odd prefix sum
int cur=0, ans=0, v={1,0}, mod=1e9+7;
for(auto a:arr){
cur^=a&1;
// if current prefix sum is even, add number of the odd prefix sum
// else add the number of even prefix sum
ans=(ans+v[1-cur])%mod;
// increase count by 1
v[cur]++;
}
return ans;
}
};

// TLE ...
// class Solution {
// public:
//     int numOfSubarrays(vector<int>& arr) {
//         int n = (int) arr.size();
//         int ans=0;
//         int mod = 1e9+7;
//         for(int i=0;i<n;i++){
//           for(int j=i, sum=0;j<n;j++){
//               sum+=arr[j];
//               if(sum&1) ans++;
//               ans%=mod;
//           }
//         }
//         return ans;
//     }
// };


/*
LeetCode - Number of Good Ways to Split a String

You are given a string s, a split is called good if you can split s into 2 non-empty strings p and q where its concatenation is equal to s and the number of distinct letters in p and q are the same.

Return the number of good splits you can make in s.

Example 1:

Input: s = "aacaba"
Output: 2
Explanation: There are 5 ways to split "aacaba" and 2 of them are good.
("a", "acaba") Left string and right string contains 1 and 3 different letters respectively.
("aa", "caba") Left string and right string contains 1 and 3 different letters respectively.
("aac", "aba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aaca", "ba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aacab", "a") Left string and right string contains 3 and 1 different letters respectively.
Example 2:

Input: s = "abcd"
Output: 1
Explanation: Split the string as follows ("ab", "cd").
Example 3:

Input: s = "aaaaa"
Output: 4
Explanation: All possible splits are good.
Example 4:

Output: 2

Constraints:

s contains only lowercase English letters.
1 <= s.length <= 10^5
*/

class Solution {
public:
int numSplits(string s) {
// sliding window approach
int n = s.size();
int l={}, r={}, ld=0, rd=0;
for(int i=0;i<n;i++){
// put all characters to r[]
// and count the distinct characters
if(++r[s[i]-'a']==1) rd++;
}
int ans=0;
for(int i=0;i<n;i++){
// put each character from r[] to l[]
// count the number of distinct characters in l[]
if(++l[s[i]-'a']==1) ld++;
// count the number of distinct characters in r[]
if(--r[s[i]-'a']==0) rd--;
// if they are equal, increase ans by 1
ans+=ld==rd;
}
return ans;
}
};


/*
LeetCode - Minimum Number of Increments on Subarrays to Form a Target Array

Given an array of positive integers target and an array initial of same size with all zeros.

Return the minimum number of operations to form a target array from initial if you are allowed to do the following operation:

Choose any subarray from initial and increment each value by one.
The answer is guaranteed to fit within the range of a 32-bit signed integer.

Example 1:

Input: target = [1,2,3,2,1]
Output: 3
Explanation: We need at least 3 operations to form the target array from the initial array.
[0,0,0,0,0] increment 1 from index 0 to 4 (inclusive).
[1,1,1,1,1] increment 1 from index 1 to 3 (inclusive).
[1,2,2,2,1] increment 1 at index 2.
[1,2,3,2,1] target array is formed.
Example 2:

Input: target = [3,1,1,2]
Output: 4
Explanation: (initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target).
Example 3:

Input: target = [3,1,5,4,2]
Output: 7
Explanation: (initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1]
-> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target).
Example 4:

Input: target = [1,1,1,1]
Output: 1

Constraints:

1 <= target.length <= 10^5
1 <= target[i] <= 10^5
*/

class Solution {
public:
int minNumberOperations(vector<int>& target) {
int pre=0, ans=0;
for(auto t:target) {
// we need t-pre operations for each character
ans+=max(t-pre,0);
pre=t;
}
return ans;
}
};


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

## wingkwong / atcoder

### Discussion   