Weekly Contest 166

Posted on | In , | |
Words count in article: 608 | Reading time ≈ 3

1281. Subtract the Product and Sum of Digits of an Integer

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int subtractProductAndSum(int n) {
        int sum = 0;
        int time = 1;
        while(n){
            sum += n % 10;
            time *= n % 10;
            n /= 10;
        }
        return  time-sum;
    }
};

1282. Group the People Given the Group Size They Belong To

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct node{
    int index;
    int key;
};

bool cmp(node& a, node&b){
    return a.key < b.key;
}

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> ret;
        vector<node> arr;
        for(int i=0; i<groupSizes.size(); i++){
            node rem;
            rem.index = i;
            rem.key = groupSizes[i];
            arr.push_back(rem);
        }
        sort(arr.begin(), arr.end(), cmp);
        int cur_max = arr[0].key;
        int cur = 0;
        vector<int> tmp;
        for(int i=0; i<arr.size(); i++){
            if(cur == cur_max){
                cur_max = arr[i].key;
                cur = 0;
                ret.push_back(tmp);
                tmp.resize(0);
            }
            tmp.push_back(arr[i].index);
            cur++;
            if(i == arr.size()-1){
                ret.push_back(tmp);
            }
        }
        return ret;
    }
};

1283. Find the Smallest Divisor Given a Threshold

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int smallestDivisor(vector<int>& A, int threshold) {
        int left = 1, right = 1e6, m, sum;
        while(left < right){
            m = (left + right) / 2, sum = 0;
            for(int i: A)
                sum += (i + m - 1) / m;
            if(sum > threshold)
                left = m + 1;
            else
                right = m;
        }
        return left;
    }
};

1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public:
    string toString(vector<vector<int>>& mat){
        string result="";
        for(int i=0; i<mat.size(); i++){
            for(int j=0; j<mat[i].size(); j++){
                result += to_string(mat[i][j])+",";
            }
        }
        return result;
    }
    int minFlips(vector<vector<int>>& mat) {
        deque<vector<vector<int>>> q={mat};
        unordered_set<string> v = {toString(mat)};
        int c = 0;
        int dx[4] = {1, 0, -1, 0};
        int dy[4] = {0, 1, 0, -1};
        int f = 0;
        for(int i=0; i<mat.size(); i++){
            for(int j=0; j<mat[i].size(); j++)
                if(mat[i][j] == 1) f = 1;
        }
        if(f == 0) return 0;
        while(q.size() > 0){
            int s = q.size();
            c++;
            for(int i=0; i<s; i++){
                vector<vector<int>> p = q.front();
                q.pop_front();
                vector<vector<int>> temp = p;
                for(int j=0; j<temp.size(); j++){
                    for(int k=0; k<temp[j].size(); k++){
                        temp[j][k]^=1; //flip 0 to 1, 1 to 0
                        for(int d=0;d<4;d++)
                        {
                            int x=j+dx[d];
                            int y=k+dy[d];
                            if(x>=0&&x<temp.size()&&y>=0&&y<temp[0].size()) temp[x][y]^=1;
                        }
                        
                        string output=toString(temp);
                        if(v.find(output)==v.end()) //if not visited yet
                        {
                            int f=0; //check if all 0s
                            for(int c1=0;c1<temp.size();c1++)
                                for(int c2=0;c2<temp[c1].size();c2++)
                                    if(temp[c1][c2]==1) f=1;

                            if(f==0) return c;
                            q.push_back(temp);
                            v.insert(output);
                        }
                        temp=p; //restore the matrix after flipping
                    }
                }
            }
        }
        return -1;
    }
};
Donate? comment?