loading...

Daily Coding Challenge #104

wingkwong profile image Wing-Kam ・8 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.


/*
Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3
Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2
*/

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // simply solved by Boyer-Moore Voting Algorithm
        // There can be at most one majority element which is more than ⌊n/2⌋ times.
        // There can be at most two majority elements which are more than ⌊n/3⌋ times.
        // There can be at most three majority elements which are more than ⌊n/4⌋ times.
        int c1, cnt1=0;
        for(int n:nums){
            if(cnt1==0) c1=n;
            if(n==c1) cnt1++;
            else cnt1--;
        }
        return c1;
    }
};


class Solution2 {
public:
    int majorityElement(vector<int>& nums) {
        int n = (int)nums.size();
        int k = n/2;
        unordered_map<int,int> m;
        for(int num:nums) m[num]++;
        for(int num:nums) {
            if(m[num]>k) return num;
        }
        return -1;
    }
};

class Solution3 {
public:
    int majorityElement(vector<int>& nums) {
        int n = (int)nums.size();
        int k = n/2;
        sort(nums.begin(),nums.end());
        return nums[k];
    }
};

static const auto io_sync_off = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/*
Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]
Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
*/

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        // simply solved by Boyer-Moore Voting Algorithm
        // There can be at most one majority element which is more than ⌊n/2⌋ times.
        // There can be at most two majority elements which are more than ⌊n/3⌋ times.
        // There can be at most three majority elements which are more than ⌊n/4⌋ times.
        vector<int> ans;
        int sz = (int) nums.size();
        if(sz==0) return ans;
        int c1=0,c2=0,cnt1=0,cnt2=0;
        for(int n:nums){
            if(n==c1) cnt1++;
            else if(n==c2) cnt2++;
            else if(cnt1==0) c1=n, cnt1=1;
            else if(cnt2==0) c2=n, cnt2=1;
            else --cnt1, --cnt2;
        }
        cnt1=0, cnt2=0;
        for(int n:nums){
            if(n==c1) cnt1++;
            else if(n==c2) cnt2++;
        }      
        if(cnt1>sz/3) ans.push_back(c1);
        if(cnt2>sz/3) ans.push_back(c2);

        return ans;
    }
};

/*
Most Visited Sector in a Circular Track

Given an integer n and an integer array rounds. We have a circular track which consists of n sectors labeled from 1 to n. A marathon will be held on this track, the marathon consists of m rounds. The ith round starts at sector rounds[i - 1] and ends at sector rounds[i]. For example, round 1 starts at sector rounds[0] and ends at sector rounds[1]

Return an array of the most visited sectors sorted in ascending order.

Notice that you circulate the track in ascending order of sector numbers in the counter-clockwise direction (See the first example).

Input: n = 4, rounds = [1,3,1,2]
Output: [1,2]
Explanation: The marathon starts at sector 1. The order of the visited sectors is as follows:
1 --> 2 --> 3 (end of round 1) --> 4 --> 1 (end of round 2) --> 2 (end of round 3 and the marathon)
We can see that both sectors 1 and 2 are visited twice and they are the most visited sectors. Sectors 3 and 4 are visited only once.
Example 2:

Input: n = 2, rounds = [2,1,2,1,2,1,2,1,2]
Output: [2]
Example 3:

Input: n = 7, rounds = [1,3,5,7]
Output: [1,2,3,4,5,6,7]


Constraints:

2 <= n <= 100
1 <= m <= 100
rounds.length == m + 1
1 <= rounds[i] <= n
rounds[i] != rounds[i + 1] for 0 <= i < m
*/


class Solution {
public:
    vector<int> mostVisited(int n, vector<int>& rounds) {
        vector<int> ans;
        // only first and last value matters
        int last = rounds.size()-1;
        // start <= end
        for(int i=rounds[0];i<=rounds[last];i++) ans.push_back(i);
        if(ans.size()>0) return ans;
        // start > end
        // [1..end] + [start..n]
        for(int i=1;i<=rounds[last];i++) ans.push_back(i);
        for(int i=rounds[0];i<=n;i++) ans.push_back(i);
        return ans;
    }
};

class Solution {
public:
    vector<int> mostVisited(int n, vector<int>& rounds) {
        vector<int> ans, cnt(n+1,0);
        // brute force - simulation 
        int i,j;
        cnt[rounds[0]]=1;
        for(i=0;i<rounds.size()-1;i++) {
            int j=rounds[i]+1;
            while(true) {
                if(j==rounds[i+1]+1) break;
                if(j==n+1) j=1;
                cnt[j++]+=1;
            }
        }
        int mx=*max_element(cnt.begin(),cnt.end());
        for(int i=1;i<=n;i++) if(cnt[i]==mx) ans.push_back(i);
        return ans;
    }
};

/*
Maximum Number of Coins You Can Get

There are 3n piles of coins of varying size, you and your friends will take piles of coins as follows:

In each step, you will choose any 3 piles of coins (not necessarily consecutive).
Of your choice, Alice will pick the pile with the maximum number of coins.
You will pick the next pile with maximum number of coins.
Your friend Bob will pick the last pile.
Repeat until there are no more piles of coins.
Given an array of integers piles where piles[i] is the number of coins in the ith pile.

Return the maximum number of coins which you can have.



Example 1:

Input: piles = [2,4,1,2,7,8]
Output: 9
Explanation: Choose the triplet (2, 7, 8), Alice Pick the pile with 8 coins, you the pile with 7 coins and Bob the last one.
Choose the triplet (1, 2, 4), Alice Pick the pile with 4 coins, you the pile with 2 coins and Bob the last one.
The maximum number of coins which you can have are: 7 + 2 = 9.
On the other hand if we choose this arrangement (1, 2, 8), (2, 4, 7) you only get 2 + 4 = 6 coins which is not optimal.
Example 2:

Input: piles = [2,4,5]
Output: 4
Example 3:

Input: piles = [9,8,7,6,5,1,2,3,4]
Output: 18


Constraints:

3 <= piles.length <= 10^5
piles.length % 3 == 0
1 <= piles[i] <= 10^4
*/

class Solution {
public:
    int maxCoins(vector<int>& piles) {
        int ans=0, n = piles.size();
        sort(piles.begin(), piles.end());
        // 2,4,1,2,7,8
        // 1,2,2,4,7,8
        // B B U A U A  (B: Bob; U: You; A: Alice)
        // Bob will take all the smallest values
        // Alice will take all the biggest values
        // You will take the rest of them
        for(int i=n/3;i<piles.size();i+=2) ans+=piles[i];
        return ans;
    }
};

/*
Find Latest Group of Size M

Given an array arr that represents a permutation of numbers from 1 to n. You have a binary string of size n that initially has all its bits set to zero.

At each step i (assuming both the binary string and arr are 1-indexed) from 1 to n, the bit at position arr[i] is set to 1. You are given an integer m and you need to find the latest step at which there exists a group of ones of length m. A group of ones is a contiguous substring of 1s such that it cannot be extended in either direction.

Return the latest step at which there exists a group of ones of length exactly m. If no such group exists, return -1.

Example 1:

Input: arr = [3,5,1,2,4], m = 1
Output: 4
Explanation:
Step 1: "00100", groups: ["1"]
Step 2: "00101", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "11101", groups: ["111", "1"]
Step 5: "11111", groups: ["11111"]
The latest step at which there exists a group of size 1 is step 4.

Example 2:

Input: arr = [3,1,5,4,2], m = 2
Output: -1
Explanation:
Step 1: "00100", groups: ["1"]
Step 2: "10100", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "10111", groups: ["1", "111"]
Step 5: "11111", groups: ["11111"]
No group of size 2 exists during any step.

Example 3:

Input: arr = [1], m = 1
Output: 1
Example 4:

Input: arr = [2,1], m = 2
Output: 2


Constraints:

n == arr.length
1 <= n <= 10^5
1 <= arr[i] <= n
All integers in arr are distinct.
1 <= m <= arr.length
*/


class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int n = arr.size(), step=0, ans=-1, cnt=0;
        // count the length of groups
        // just update the leftmost and the rightmost of the group
        vector<int> len(n+2,0);
        for(int i=0;i<n;i++){
            ++step;
            int a=arr[i], left=len[a-1], right=len[a+1];
            len[a-left]=len[a+right]=left+right+1;
            cnt-=(left==m);
            cnt-=(right==m);
            cnt+=(left+right+1==m);
            if(cnt) ans=step;
        }
        return ans;
    }
};



/*
Stone Game V

There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.

In each round of the game, Alice divides the row into two non-empty rows (i.e. left row and right row), then Bob calculates the value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and Alice's score increases by the value of the remaining row. If the value of the two rows are equal, Bob lets Alice decide which row will be thrown away. The next round starts with the remaining row.

The game ends when there is only one stone remaining. Alice's is initially zero.

Return the maximum score that Alice can obtain.



Example 1:

Input: stoneValue = [6,2,3,4,5,5]
Output: 18
Explanation: In the first round, Alice divides the row to [6,2,3], [4,5,5]. The left row has the value 11 and the right row has value 14. Bob throws away the right row and Alice's score is now 11.
In the second round Alice divides the row to [6], [2,3]. This time Bob throws away the left row and Alice's score becomes 16 (11 + 5).
The last round Alice has only one choice to divide the row which is [2], [3]. Bob throws away the right row and Alice's score is now 18 (16 + 2). The game ends because only one stone is remaining in the row.
Example 2:

Input: stoneValue = [7,7,7,7,7,7,7]
Output: 28
Example 3:

Input: stoneValue = [4]
Output: 0


Constraints:

1 <= stoneValue.length <= 500
1 <= stoneValue[i] <= 10^6
*/

class Solution {
public:
    int dp[505][505] = {0};
    // dfs approach 
    int dfs(vector<int>& stoneValue, int i, int j){
        if(!dp[i][j]){
            for(int k=i;k<j;k++){
                int left = stoneValue[k]-(i?stoneValue[i-1]:0), right=stoneValue[j]-stoneValue[k];
                // left > right - right + dfs left part
                // left < right - left + dfs right part
                // left = right - dfs left and right part
                if(left<=right) dp[i][j] = max(dp[i][j], left + dfs(stoneValue,i,k));
                if(left>=right) dp[i][j] = max(dp[i][j], right + dfs(stoneValue,k+1,j));
            }
        }
        return dp[i][j];
    }

    int stoneGameV(vector<int>& stoneValue) {
        // use STL to calculate prefix sum
        partial_sum(stoneValue.begin(), stoneValue.end(), stoneValue.begin());
        return dfs(stoneValue,0,stoneValue.size()-1);
    }
};

There are other programming solutions in the following repositories below. Star and watch for timely updates!

GitHub logo wingkwong / competitive-programming

🌟 My CP Journey - This repository contains CP solutions (mostly written in C++) from different OJs and contest sites 🌟

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

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

Discussion

pic
Editor guide