Leetcode 118.Pascal's Triangle

 Problem Link: Click

This is a simple pascal triangle problem. One matter we have to keep in mind is we may have resize the vector size and allocate them carefully. Hence we have to return the vector.

Code:

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int> > vec(numRows);
        for(int i=0;i<numRows;i++){
            vec[i].resize(i+1);
            vec[i][0]=1;
            vec[i][i]=1;
        }
        for(int i=2;i<numRows;i++){
            for(int j=1;j<i;j++){
                vec[i][j]=vec[i-1][j]+vec[i-1][j-1];
            }
        }
        return vec;
    }
};

Leetcode 73. Set Matrix Zeroes

 Problem link:click

This is very easy problem. In this problem you have to make all elements of a row or a column to zero if any element of the matrix of the specific row or column is zero. For this purpose we can take the first row and the first column as a flag of the row and column. If any element of a row or column is zero we will make the flag of first row and columns as zero.

For making all elements of the row and column zero we just have to check if matrix[i][0]==0 or matrix[0][j]==0.

Code:

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int col=matrix[0].size(),row=matrix.size(),col0=1;
        for(int i=0;i<row;i++){
            if(matrix[i][0]==0)col0=0;
            for(int j=1;j<col;j++){
                if(matrix[i][j]==0){
                    matrix[0][j]=0;
                    matrix[i][0]=0;
                }
            }
        }
        for(int i=row-1;i>=0;i--){
            for(int j=col-1;j>=1;j--){
                if(matrix[i][0]==0 || matrix[0][j]==0){
                    matrix[i][j]=0;
                }
            }
            if(col0==0)matrix[i][0]=0;
        }
    }
};

Another Problem About Dividing Numbers :: Codeforces Round 725 D

Problem link

In this problem you will be given two integer number a and b. You need to make a and b equal in exactly k operation(s).  In one operation you can either,

• Take an integer c (c>1 and a should be divisible by c) and replace a with ac
  
• Take an integer c
(c>1and b should be divisible by c) and replace b with bc.

Observations: If we at least  need x moves to make a and b equal and we have at most y moves which is total number of moves we can make in total. A move is choosing such a C discussing above. Then we can also make a and b equal by x+1,x+2,x+3.......y-2,y-1,y moves. [for better understanding a paperwork may help]

Explanation:

For finding the minimum number of moves to make a and b (if a!=b) are equal will be 1 or 2. 

>>if gcd(a,b)==min(a,b) then it will be 1.

lets say, a=36 and b=12;

gcd(36,12) = min(36,12) = 12 

we can make a=12 by dividing 36 by 3 in one move.

>>if gcd(a,b)!=min(a,b) then it will be 2. Because we need to divide both a and b to make equal to its gcd.

For finding the at most moves we have, we had to find number of prime factors both for a and b. because at most we can divide them until they left any prime factors.

For calculating the Number of prime factors. we will be needed prime numbers. For this purpose a simple sieve will work fine.

Code:

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 61 62 63 64 65 66 67 68 69 70 71 72

#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define int long long #define IOS ios::sync_with_stdio(false); int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);} const int maxn=100005; bitset<maxn+5>bs; vector<int> prime; void seive(){ bs.set(); bs[0]=0; bs[1]=0; for(int i=2;i<maxn;i++){ if(bs[i]){ prime.pb(i); for(int j = i*i; j<maxn;j+=i)bs[j]=0; } } } ///solution void solution(){ int a,b,k; cin>>a>>b>>k; if(a==b && k==1){ cout << "NO\n"; return; } int cnta=0,cntb=0,now=a; for(auto it:prime){ if(it*it>now){ break; } while(now%it == 0){ now/=it; cnta++; } } if(now>1)cnta++; now=b; for(auto it:prime){ if(it*it>now )break; while(now%it == 0){ now/=it; cntb++; } } if(now>1)cntb++; int x=gcd(a,b); int atmost=cnta+cntb,least=0; if(x==min(a,b))least=1; else least=2; if(least<=k && atmost>=k){ cout << "YES\n"; } else cout << "NO\n"; } signed main() { IOS int t; t=1; seive(); cin>>t; while(t--){ solution(); } return 0; }