loading...

Daily Coding Challenge #118

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


/*
Task Hare
https://binarysearch.io/problems/Task-Hare

You are given a list of integers tasks and another list of integers people. The integer tasks[i] represents the amount of strength required to perform the ith task. people[i] represents the amount of strength the ith person has.

Return the number of tasks that can be finished if one person can perform at most one task.

Constraints

n ≤ 100,000 where n is the length of tasks
m ≤ 100,000 where m is the length of people
Example 1
Input

tasks = [3, 2, 9, 13]
people = [10, 5, 2, 1]
Output

3
Explanation

First person can perform task 9
Second person can perform task 3
Third person can perform task 2
Fourth person can't perform any tasks
*/

#include "solution.hpp"
using namespace std;


class Solution {
    public:
    int solve(vector<int>& tasks, vector<int>& people) {
        sort(tasks.begin(), tasks.end());
        sort(people.begin(), people.end());
        int j=0;
        for(int i=0;i<people.size();i++){
            if(j<tasks.size()&&people[i]>=tasks[j]){
                j++;
            }
        }
        return j;
    }
};

class Solution2 {
    public:
    int solve(vector<int>& tasks, vector<int>& people) {
        sort(tasks.rbegin(), tasks.rend());
        sort(people.rbegin(), people.rend());
        int ans=0, j=0;
        for(int i=0;i<people.size();i++){
            while(j<tasks.size()){
                if(people[i]<tasks[j]){
                    j++;
                } else {
                    ans++;
                    j++;
                    break;
                }
            }
        }
        return ans;
    }
};


/*
Maximum Product Subarray
https://leetcode.com/problems/maximum-product-subarray/

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
*/

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int mx, mi, ans;
        mx=mi=ans=nums[0];
        for(int i=1;i<nums.size();i++){
            int tmp=mx;
            mx=max({nums[i],nums[i]*mx,nums[i]*mi});
            mi=min({nums[i],nums[i]*tmp,nums[i]*mi});
            ans=max(ans,mx);
        }
        return ans;
    }
};

class Solution2 {
public:
    int maxProduct(vector<int>& nums) {
        int n=(int)nums.size(), l=nums[0], r=nums[n-1], ans=nums[0];
        for(int i=1;i<n;i++){
            l*=nums[i];
            r*=nums[n-1-i];
            ans=max({ans,l,r});
        }
        return ans;
    }
};

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

markdown guide