loading...

Daily Coding Challenge #77

wingkwong profile image Wing-Kam ・4 min read

About

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 [9].

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],[1,3],[1,3,5],[3],[3,5],[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],[2,4],[2,4,6],[4],[4,6],[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 = [7]
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[0]: even prefix sum
        // v[1]: odd prefix sum
        int cur=0, ans=0, v[2]={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:

Input: s = "acbadbaada"
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[26]={}, r[26]={}, 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!

GitHub logo wingkwong / leetcode

🏆 A Collection of my LeetCode Solutions with Explanations 🏆

GitHub logo wingkwong / hackerrank

🏆 A Collection of my HackerRank Solutions with Explanations 🏆

GitHub logo wingkwong / codeforces

🏆 A Collection of my Codeforces Solutions with Explanations 🏆

GitHub logo wingkwong / atcoder

🏆 A Collection of my AtCoder Solutions with Explanations 🏆

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

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

Discussion

markdown guide