loading...

Daily Coding Challenge #96

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 - Three Consecutive Odds

Given an integer array arr, return true if there are three consecutive odd numbers in the array. Otherwise, return false.


Example 1:

Input: arr = [2,6,4,1]
Output: false
Explanation: There are no three consecutive odds.
Example 2:

Input: arr = [1,2,34,3,4,5,7,23,12]
Output: true
Explanation: [5,7,23] are three consecutive odds.


Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
*/

class Solution {
public:
    bool threeConsecutiveOdds(vector<int>& arr) {
        int cnt=0;
        // count 3 consecutive odds.. 
        for(int x:arr){
            if(x&1) cnt++;
            else cnt=0;
            if(cnt==3) return true;
        }
        return false;
    }
};

/*
LeetCode - Minimum Operations to Make Array Equal

You have an array arr of length n where arr[i] = (2 * i) + 1 for all valid values of i (i.e. 0 <= i < n).

In one operation, you can select two indices x and y where 0 <= x, y < n and subtract 1 from arr[x] and add 1 to arr[y] (i.e. perform arr[x] -=1 and arr[y] += 1). The goal is to make all the elements of the array equal. It is guaranteed that all the elements of the array can be made equal using some operations.

Given an integer n, the length of the array. Return the minimum number of operations needed to make all the elements of arr equal.



Example 1:

Input: n = 3
Output: 2
Explanation: arr = [1, 3, 5]
First operation choose x = 2 and y = 0, this leads arr to be [2, 3, 4]
In the second operation choose x = 2 and y = 0 again, thus arr = [3, 3, 3].
Example 2:

Input: n = 6
Output: 9
*/

class Solution {
public:
    int minOperations(int n) {
        int ans=0;
        // convert all numbers to n/2
        for(int i=n-1;i>=n/2;i--) 
            ans+=(2*i+1)-n;
        return ans;
    }
};


/*
LeetCode - Minimum Number of Days to Eat N Oranges

There are n oranges in the kitchen and you decided to eat some of these oranges every day as follows:

Eat one orange.
If the number of remaining oranges (n) is divisible by 2 then you can eat  n/2 oranges.
If the number of remaining oranges (n) is divisible by 3 then you can eat  2*(n/3) oranges.
You can only choose one of the actions per day.

Return the minimum number of days to eat n oranges.



Example 1:

Input: n = 10
Output: 4
Explanation: You have 10 oranges.
Day 1: Eat 1 orange,  10 - 1 = 9.  
Day 2: Eat 6 oranges, 9 - 2*(9/3) = 9 - 6 = 3. (Since 9 is divisible by 3)
Day 3: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. 
Day 4: Eat the last orange  1 - 1  = 0.
You need at least 4 days to eat the 10 oranges.
Example 2:

Input: n = 6
Output: 3
Explanation: You have 6 oranges.
Day 1: Eat 3 oranges, 6 - 6/2 = 6 - 3 = 3. (Since 6 is divisible by 2).
Day 2: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. (Since 3 is divisible by 3)
Day 3: Eat the last orange  1 - 1  = 0.
You need at least 3 days to eat the 6 oranges.
Example 3:

Input: n = 1
Output: 1
Example 4:

Input: n = 56
Output: 6


Constraints:

1 <= n <= 2*10^9
*/

class Solution {
public:
    unordered_map<int,int> dp;
    int minDays(int n) {
        if(n<=1) return n;
        if(!dp.count(n)) {
            dp[n]=1+min(n%2+minDays(n/2),n%3+minDays(n/3));
        }
        return dp[n];
    }
};

/*
LeetCode - Magnetic Force Between Two Balls

In universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the ith basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.

Rick stated that magnetic force between two different balls at positions x and y is |x - y|.

Given the integer array position and the integer m. Return the required force.



Example 1:


Input: position = [1,2,3,4,7], m = 3
Output: 3
Explanation: Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.
Example 2:

Input: position = [5,4,3,2,1,1000000000], m = 2
Output: 999999999
Explanation: We can use baskets 1 and 1000000000.


Constraints:

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

class Solution {
public:
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(),position.end());
        // binary search
        int l=0, r=1e9;
        while(l<r){
            int m=l+(r-l)/2, last=-1e9, cnt=0;
            for(int p:position){
                if(last+m<=p){
                    last=p;
                    cnt++;
                }
            }
            if(cnt<m) r=m-1;
            else l=m;
        }
        return l;
    }
};


There are other programming solutions in the following repositories 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 🏆

GitHub logo wingkwong / cses

🏆 A Collection of my CSES Solutions with Explanations 🏆

GitHub logo wingkwong / timus

A Collection of my Timus Solutions

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

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

Discussion

pic
Editor guide