TCS Online Communities Even Groups CodeVita Problem [Solved]

Rajeev Reddy Nareddula 7/02/2018

Problem : Online Communities - Even Groups

In a social network, online communities refer to the group of people with an interest towards the same topic. People connect with each other in a social network. A connection between Person I and Person J is represented as C I J. When two persons belonging to different communities connect, the net effect is merger of both communities which I and J belonged to.

We are only interested in finding out the communities with the member count being an even number. Your task is to find out those communities.

Input Format:

Input will consist of three parts, viz.

1. The total number of people on the social network (N)
2.Queries 

• C I J, connect I and J
• Q 0 0, print the number of communities with even member-count

-1 will represent end of input.

Output Format:

For each query Q, output the number of communities with even member-count

Constraints:

1<=N<=10^6

1<=I, J<=N

Sample Input and Output

SNo.	Input	Output
1	5 Q 0 0 C 1 2 Q 0 0 C 2 3 Q 0 0 C 4 5 Q 0 0 -1	0 1 0 1

Solution:

//Problem: Online communities- Even groups

#include<iostream>
using namespace std;
int comm[1000001],n;
void mergecom(int,int);
//void print();
int even(int);
int main(){
    int x,y,comNo=1;
    char c;
    cin>>n;
    while(true){
        cin>>c;
        if(c=='C'){
            cin>>x>>y;
            if(comm[x]==0 && comm[y]==0){
                comm[x]=comm[y]=comNo;
                comNo++;
            }
            else if(comm[x]==0){
                comm[x]=comm[y];
            }
            else if(comm[y]==0){
                comm[y]=comm[x];
            }
            else if(comm[x]>comm[y]){
                mergecom(comm[y],comm[x]);
                comNo--;
            }
            else if(comm[y]>comm[x]){
                mergecom(comm[x],comm[y]);
                comNo--;
            }
        }
        else if(c=='Q'){
            cin>>x>>y;
            cout<<even(comNo)<<endl;
        }
        else
            break;
    }

return 0;
}

void mergecom(int x,int y){
    for(int i=0;i<=n;i++){
        if(comm[i]==y)
            comm[i]=x;
        else if(comm[i]>y)
            comm[i]--;
    }
}
int even(int comNo){
int count =0,temp=0;
for(int i=1;i<comNo;i++){
    for(int j=0;j<=n;j++){
        if(comm[j]==i)
            temp++;
    }
    if(temp%2==0 && temp!=0){
        count++;
    }
    temp=0;
}
return count;
}
/*
void print(){
for(int i=0;i<=n;i++)
    cout<<i<<comm[i]<<" ";
cout<<endl;
}*/

Consider the following example. 

Dhaniram wants to buy a TV. He needs to pay Rs 2000/- per month for 12 installments to own the TV. If let's say he gets 4% interest per annum on his savings bank account, then Dhaniram will need to deposit a certain amount in the bank today, such that he is able to withdraw Rs 2000/- per month for the next 12 months without requiring any additional deposits throughout. 

Your task is to find out how much Dhaniram should deposit today so that he gets assured cash flows for a fixed period in the future, given the rate of interest at which his money will grow during this period. 

Input Format: 

First line contains desired cash flow M 

Second line contains period in months denoted by T 

Third line contains rate per annum R expressed in percentage at which deposited amount will grow 

Output Format: 

Print total amount of money to be deposited now rounded off to the nearest integer 

Constraints:

M > 0

T > 0

R >= 0

Calculation should be done upto 11-digit precision

Sample Input and Output

SNo. Input Output

1 

500

3

12

1470

2 

6000

3

5.9

17824

3 

500

2

0

1000

Highlights

• Understand the problem statement thoroughly.
• Break down the problem into smaller subproblems.
• Design an algorithm to solve each subproblem.
• Implement the algorithm in your preferred programming language.
• Test your solution with sample inputs and edge cases.
• Optimize your solution if necessary.