TCS NQT || Coding Question and Solution || 23rd August || 2022 || Set - 4 || Mahesh and Suresh

Question

Link to all the TCS_NQT Coding Questions and Answers of year 2022 : https://www.desiqna.in/tag/tcs_nqt

Answer 1

Code Question : 

Answer 2

C++ code : 

// C++Program to count islands in boolean 2D matrix
#include <bits/stdc++.h>
using namespace std;
typedef int ll ; 
int v ; 
vector <int> b ; 
    int N1,N2 ; 
void DFS(vector<vector<int>> &M, int i, int j, int ROW,
        int COL)
{
    //Base condition
    //if i less than 0 or j less than 0 or i greater than ROW-1 or j greater than COL- or if M[i][j] != 1 then we will simply return
    if (i < 0 || j < 0 || i > (ROW - 1) || j > (COL - 1) || M[i][j] != 1)
    {
        return;
    }

    if (M[i][j] == 1)
    {
        v++;
        M[i][j] = 0;
        DFS(M, i + 1, j, ROW, COL);     //right side traversal
        DFS(M, i - 1, j, ROW, COL);     //left side traversal
        DFS(M, i, j + 1, ROW, COL);     //upward side traversal
        DFS(M, i, j - 1, ROW, COL);     //downward side traversal
    
    }
}

int countIslands(vector<vector<int>> &M)
{
    int ROW = M.size();
    int COL = M[0].size();
    int count = 0;
    for (int i = 0; i < ROW; i++)
    {
        for (int j = 0; j < COL; j++)
        {
            if (M[i][j] == 1)
            {
                v = 0 ; 
                M[i][j] = 0;
                count++; v++ ; 
                DFS(M, i + 1, j, ROW, COL);     //right side traversal
                DFS(M, i - 1, j, ROW, COL);     //left side traversal
                DFS(M, i, j + 1, ROW, COL);     //upward side traversal
                DFS(M, i, j - 1, ROW, COL);     //downward side traversal
                //cout<<i<<" "<<j<<" "<<v;
                b.push_back(v);
                //cout<<"\n";
            }
        }
    }
    return count;
}

// Driver Code
int main()
{
//     vector<vector<int>> M = {{1, 1, 0, 0, 0},
//                             {0, 1, 0, 0, 1},
//                             {1, 0, 0, 1, 1},
//                             {0, 0, 0, 0, 0},
//                             {1, 0, 1, 0, 1}};

    
    vector<vector<int>> M ; 

    cin>>N1>>N2;
    
    int i = 0 ; 
    while(i<N1){
        
        vector <ll> p ; 
        int j = 0 ; 
        while(j<N2){
            char g ;
            cin>>g ; 
            if(g=='0'){
                p.push_back(0);
            }
            else{
                p.push_back(1);
            }
            j++;
        }
        M.push_back(p);
        
        i++;
    }
    
    ll ookkkkk =  countIslands(M);
    sort(b.begin(),b.end());
    reverse(b.begin(),b.end());
    ll n = b.size();
    i = 0 ;ll g1 = 0 ; ll g2 = 0 ; 
    while(i<n){
        if(i%2==0){
            g1 = g1 + b[i];
        }else{
            g2 = g2 + b[i] ; 
        }
        
        i++;
    }
    
    cout<<g2 ; 
    
    return 0;
}