# Friends | CodeChef Solution

Hello coders, today we are going to solve Friends CodeChef Solution whose Problem Code is RRFRNDS.

After IOI Ilya decided to make a business. He found a social network called “TheScorpyBook.com”. It currently hasÂ NÂ registered users. As in any social network two users can be friends. Ilya wants the world to be as connected as possible, so he wants to suggest friendship to some pairs of users. He will suggest userÂ uÂ to have a friendship with userÂ vÂ if they are not friends yet and there is a userÂ wÂ who is friends of both of them. Note thatÂ u,Â vÂ andÂ wÂ are different users. Ilya is too busy with IPO these days, so he asks you to count how many friendship suggestions he has to send over his social network.

## Input Format

The first line contains an integer numberÂ NÂ â€” the number of users in the network. NextÂ NÂ lines containÂ NÂ characters each denoting friendship relations.Â jthÂ character if theÂ ithÂ lines equals one, if usersÂ iÂ andÂ jÂ are friends and equals to zero otherwise. This relation is symmetric, i.e. if userÂ aÂ is friend ofÂ bÂ thenÂ bÂ is also a friend ofÂ a.

## Output Format

Output a single integer â€” number of friendship suggestions Ilya has to send.

## Constraints

• 1Â â‰¤Â NÂ â‰¤Â 2000

Example

Sample Input

``````4
0111
1000
1000
1000
``````

Sample Output

``6``

Explanation

Each of usersÂ [2, 3, 4]Â should receive two friendship suggestions, while userÂ 1Â does not need any, since he already has all other users in his friend-list.

## Solution – Friends

### C++

```#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <complex>
#include <queue>
#include <set>
#include <unordered_set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <fstream>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
ll MOD = 998244353;
double eps = 1e-12;
#define forn(i,e) for(ll i = 0; i < e; i++)
#define forsn(i,s,e) for(ll i = s; i < e; i++)
#define rforn(i,s) for(ll i = s; i >= 0; i--)
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 2e18
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())

void solve(){
int n;
cin>>n;

vector<bitset<2001>> friends(n);

for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
char m;
cin>>m;

if(i==j)
{
continue;
}
else{
if(m=='1')
{

friends[i].set(j);
}
}
}
}

int sugg_count = 0;

for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(!friends[i][j])
{
bitset<2001> common = friends[i] & friends[j];

if(common.any())
{
sugg_count+=2;
}
}
}
}

cout<<sugg_count<<endl;
}
int main()
{
fast_cin();

solve();
return 0;
}```

### Python

```n=int(input())
l=[]
l2=[]
c=0
m=[]
for i in range(n):
f=input()
sub=set()
l3=['0'*(8-len(x))+x for x in f]
l2.append(l3)
m.append(int(f,2))

for i in range(n-1):
for j in range(i+1,n):
if l2[i][j][-1]=='0' and m[i]&m[j]!=0:
c+=2
print(c)
```

### Java

```import java.util.ArrayList;
import java.util.BitSet;
import java.util.Scanner;
class Friends {

public static void main(String[] args)  {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), ans = 0;
sc.nextLine();
ArrayList<BitSet> graph = new ArrayList<BitSet>();
for (int i = 0; i < n; i++) {
String str = sc.nextLine();
for (int j = 0; j < str.length(); j++) {
if (str.charAt(j) == '1') {
graph.get(i).set(j);
}
}
}
for (int i = 0; i < n; i++) {
BitSet bt = graph.get(i);
for (int j = 0; j < n; j++) {
if (j != i && !bt.get(j)) {
if (bt.intersects(graph.get(j))) {
ans++;
}
}
}
}
System.out.println(ans);

}

}
```

Disclaimer: The above Problem (Friends) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.