Table of Contents
Jogging Cats – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Jogging Cats HackerRank Solution
#include <iostream>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#include <cstdio>
#include <map>
#include <stack>
#include <set>
#include <algorithm>
#define ll long long
using namespace std;
const int Maxn = 100010 , Maxm = 11, Mo = 1e9 + 7;
const ll oo = 1ll << 60;
#define PB push_back
int T, cs = 1;
int n , m , k;
vector<int> e[Maxn];
int cnt[Maxn];
int main(){
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++){
cin >> u >> v;
e[u].PB(v);
e[v].PB(u);
}
ll ans = 0;
for (int u = 1; u <= n; u++){
vector<int> all;
for (int i = 0; i < e[u].size(); i++){
int v = e[u][i];
for (int k =0; k < e[v].size(); k++){
int t = e[v][k];
if (t == u) continue;
if (cnt[t] == 0) all.PB(t);
ans += cnt[t];
cnt[t] ++;
}
}
for (int i = 0; i < all.size(); i++) cnt[all[i]] = 0;
}
cout << ans / 4 << endl;
}
Java Jogging Cats HackerRank Solution
#include <iostream>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#include <cstdio>
#include <map>
#include <stack>
#include <set>
#include <algorithm>
#define ll long long
using namespace std;
const int Maxn = 100010 , Maxm = 11, Mo = 1e9 + 7;
const ll oo = 1ll << 60;
#define PB push_back
int T, cs = 1;
int n , m , k;
vector<int> e[Maxn];
int cnt[Maxn];
int main(){
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++){
cin >> u >> v;
e[u].PB(v);
e[v].PB(u);
}
ll ans = 0;
for (int u = 1; u <= n; u++){
vector<int> all;
for (int i = 0; i < e[u].size(); i++){
int v = e[u][i];
for (int k =0; k < e[v].size(); k++){
int t = e[v][k];
if (t == u) continue;
if (cnt[t] == 0) all.PB(t);
ans += cnt[t];
cnt[t] ++;
}
}
for (int i = 0; i < all.size(); i++) cnt[all[i]] = 0;
}
cout << ans / 4 << endl;
}
Python 3 Jogging Cats HackerRank Solution
def joggingCats(n,m,graph):
result = 0
visited = set([])
for source,destinations in graph.items():
destinationCount = {}
for x in destinations:
if x not in visited and x in graph:
for y in graph[x]:
if y not in visited:
try:
destinationCount[y] += 1
except:
destinationCount[y] = 1
for node,count in destinationCount.items():
if node != source:
result+= count*(count-1)//2
visited.add(source)
return result
if __name__ == '__main__':
n,m = [int(i) for i in input().strip().split()]
graph = {}
for _ in range(m):
x,y = [int(i) for i in input().strip().split()]
try:
graph[x].append(y)
except:
graph[x] = [y]
try:
graph[y].append(x)
except:
graph[y] = [x]
print(joggingCats(n,m,graph))
Python 2 Jogging Cats HackerRank Solution
def solve2(n,m,d):
r = 0
s = set([])
for k,v in d.items():
dc = {}
for x in v:
if x not in s and x in d:
for y in d[x]:
if y not in s:
if y in dc: dc[y] += 1
else: dc[y] = 1
for node,c in dc.items():
if node != k: r += c*(c-1)/2
s.add(k)
return r
n,m = map(int,raw_input().strip().split())
d = {}
for i in xrange(m):
x,y = map(int,raw_input().strip().split())
if x in d: d[x].append(y)
else: d[x] = [y]
if y in d: d[y].append(x)
else: d[y] = [x]
print solve2(n,m,d)
C Jogging Cats HackerRank Solution
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* readline();
char** split_string(char*);
struct edge{
int from;
int to;
};
bool precedge(struct edge e1, struct edge e2){
return e1.from < e2.from || (e1.from == e2.from && e1.to < e2.to);
}
void setup(int n, int m, int** edges, struct edge *sortedge, int* edgebds){
for(int i = 0; i < m; i++){
sortedge[2*i].from = edges[i][0] - 1;
sortedge[2*i].to = edges[i][1] - 1;
sortedge[2*i + 1].from = edges[i][1] - 1;
sortedge[2*i + 1].to = edges[i][0] - 1;
}
for(int i = 0; i < 2*m; i++){
int curr = i;
while(curr > 0){
int next = (curr - 1)/2;
if(precedge(sortedge[next], sortedge[curr])){
struct edge temp = sortedge[curr];
sortedge[curr] = sortedge[next];
sortedge[next] = temp;
curr = next;
}
else{
break;
}
}
}
for(int i = 2*m - 1; i >= 0; i--){
struct edge temp = sortedge[0];
sortedge[0] = sortedge[i];
sortedge[i] = temp;
int curr = 0;
while(true){
int next = curr;
if(2*curr + 1 < i && precedge(sortedge[next], sortedge[2*curr + 1])){
next = 2*curr + 1;
}
if(2*curr + 2 < i && precedge(sortedge[next], sortedge[2*curr + 2])){
next = 2*curr + 2;
}
if(next != curr){
struct edge temp = sortedge[curr];
sortedge[curr] = sortedge[next];
sortedge[next] = temp;
curr = next;
}
else{
break;
}
}
}
edgebds[0] = 0;
for(int i = 0; i < n; i++){
int index = edgebds[i];
while(index < 2*m && sortedge[index].from == i){
index++;
}
edgebds[i + 1] = index;
}
}
long jogroutes(int n, int m, int** edges){
struct edge sortedge[2*m];
int edgebounds[n + 1];
setup(n, m, edges, sortedge, edgebounds);
long toreturn = 0;
for(int i = 0; i < n; i++){
int start = edgebounds[i];
for(; start < edgebounds[i + 1] && sortedge[start].to < i; start++);
int numneighbors = edgebounds[i + 1] - start;
if(numneighbors > 50){
for(int j = i + 1; j < n; j++){
if(edgebounds[j] + 1 < edgebounds[j + 1]){
long common = 0;
int index1 = start;
int index2 = edgebounds[j];
while(index1 < edgebounds[i + 1] && index2 < edgebounds[j + 1]){
if(sortedge[index1].to == sortedge[index2].to){
common++;
index1++;
index2++;
}
else if(sortedge[index1].to > sortedge[index2].to){
index2++;
}
else{
index1++;
}
}
toreturn += common*(common - 1);
}
}
}
else{
for(int j = start; j < edgebounds[i + 1]; j++){
int node1 = sortedge[j].to;
int nextstart = edgebounds[node1];
for(; nextstart < edgebounds[node1 + 1] && sortedge[nextstart].to <= i; nextstart++);
for(int k = j + 1; k < edgebounds[i + 1]; k++){
int node2 = sortedge[k].to;
int index1 = nextstart;
int index2 = edgebounds[node2];
while (index1 < edgebounds[node1 + 1] && index2 < edgebounds[node2 + 1]){
if(sortedge[index1].to == sortedge[index2].to){
toreturn += 2;
index1++;
index2++;
}
else if(sortedge[index1].to > sortedge[index2].to){
index2++;
}
else{
index1++;
}
}
}
}
}
}
return toreturn/2;
}
int main() {
int n, m;
scanf("%d %d\n", &n, &m);
int** edges = malloc(m*sizeof(int*));
for(int i = 0; i < m; i++){
edges[i] = malloc(2*sizeof(int));
scanf("%d %d\n", edges[i], edges[i] + 1);
}
long result = jogroutes(n, m, edges);
printf("%ld", result);
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) { break; }
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }
size_t new_length = alloc_length << 1;
data = realloc(data, new_length);
if (!data) { break; }
alloc_length = new_length;
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}
data = realloc(data, data_length);
return data;
}
char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");
int spaces = 0;
while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}
splits[spaces - 1] = token;
token = strtok(NULL, " ");
}
return splits;
}
Leave a comment below
