Table of Contents
Toll Cost Digits – 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++ Toll Cost Digits HackerRank Solution
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }
struct UnionFind {
vector<int> data;
void init(int n) { data.assign(n, -1); }
bool unionSet(int x, int y) {
x = root(x); y = root(y);
if (x != y) {
if (data[y] < data[x]) swap(x, y);
data[x] += data[y]; data[y] = x;
}
return x != y;
}
bool findSet(int x, int y) { return root(x) == root(y); }
int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
int size(int x) { return -data[root(x)]; }
};
int main() {
int n; int m;
while (~scanf("%d%d", &n, &m)) {
UnionFind uf;
uf.init(n * 10);
for (int i = 0; i < m; ++ i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w), -- u, -- v;
rep(j, 10)
uf.unionSet(u * 10 + j, v * 10 + (j + w) % 10);
}
vector<array<int,10>> counts(n * 10);
rep(i, n) rep(j, 10)
++ counts[uf.root(i * 10 + j)][j];
rep(d, 10) {
ll ans = 0;
rep(a, n * 10) {
rep(x, 1)
ans += (ll)counts[a][x] * counts[a][(x + d) % 10];
}
rep(i, n)
ans -= uf.findSet(i * 10, i * 10 + d);
printf("%lld\n", ans);
}
}
return 0;
}
Java Toll Cost Digits HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Queue;
public class E {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni(), m = ni();
int[] from = new int[m];
int[] to = new int[m];
int[] w = new int[m];
for(int i = 0;i < m;i++){
from[i] = ni()-1;
to[i] = ni()-1;
w[i] = ni()%10;
}
int[][][] g = packWU(n, from, to, w);
int[] d = new int[n];
Arrays.fill(d, -1);
DJSet ds = new DJSet(n);
long[] ret = new long[10];
for(int i = 0;i < n;i++){
if(d[i] == -1){
Queue<Integer> q = new ArrayDeque<>();
q.add(i);
d[i] = 0;
boolean c1 = false, c2 = false, c5 = false;
int[] f = new int[10];
f[0]++;
int num = 1;
while(!q.isEmpty()){
int cur = q.poll();
for(int[] e : g[cur]){
if(d[e[0]] == -1){
d[e[0]] = (d[cur] + e[1])%10;
f[d[e[0]]]++;
num++;
q.add(e[0]);
}else{
int x = (d[cur]+e[1]+10-d[e[0]])%10;
if(x != 0){
x = gcd(x, 10);
if(x == 1){
c1 = true;
}else if(x == 2){
c2 = true;
}else{
c5 = true;
}
}
}
}
}
long[] xf = new long[10];
for(int j = 0;j < 10;j++){
for(int k = 0;k < 10;k++){
xf[(k+10-j)%10] += (long)f[j]*f[k];
}
}
xf[0] -= num;
if(c2 && c5)c1 = true;
if(c1){
for(int j = 0;j < 10;j++){
for(int k = 0;k < 10;k++){
ret[k] += xf[j];
}
}
}else if(c2){
for(int j = 0;j < 10;j++){
for(int k = 0;k < 10;k+=2){
ret[(j+k)%10] += xf[j];
}
}
}else if(c5){
for(int j = 0;j < 10;j++){
for(int k = 0;k < 10;k+=5){
ret[(j+k)%10] += xf[j];
}
}
}else{
for(int j = 0;j < 10;j++){
ret[j] += xf[j];
}
}
}
}
for(long re : ret){
out.println(re);
}
}
public static int gcd(int a, int b) {
while (b > 0) {
int c = a;
a = b;
b = c % b;
}
return a;
}
public static class DJSet {
public int[] upper;
public DJSet(int n) {
upper = new int[n];
Arrays.fill(upper, -1);
}
public int root(int x) {
return upper[x] < 0 ? x : (upper[x] = root(upper[x]));
}
public boolean equiv(int x, int y) {
return root(x) == root(y);
}
public boolean union(int x, int y) {
x = root(x);
y = root(y);
if (x != y) {
if (upper[y] < upper[x]) {
int d = x;
x = y;
y = d;
}
upper[x] += upper[y];
upper[y] = x;
}
return x == y;
}
public int count() {
int ct = 0;
for (int u : upper)
if (u < 0)
ct++;
return ct;
}
}
public static int[][][] packWU(int n, int[] from, int[] to, int[] w) {
int[][][] g = new int[n][][];
int[] p = new int[n];
for (int f : from)
p[f]++;
for (int t : to)
p[t]++;
for (int i = 0; i < n; i++)
g[i] = new int[p[i]][2];
for (int i = 0; i < from.length; i++) {
--p[from[i]];
g[from[i]][p[from[i]]][0] = to[i];
g[from[i]][p[from[i]]][1] = w[i];
--p[to[i]];
g[to[i]][p[to[i]]][0] = from[i];
g[to[i]][p[to[i]]][1] = (10-w[i])%10;
}
return g;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new E().run(); }
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Python 3 Toll Cost Digits HackerRank Solution
from collections import deque
from collections import defaultdict
# Enter your code here. Read input from STDIN. Print output to STDOUT
n,e = [int(x) for x in input().split()]
kop = defaultdict(set)
gran = defaultdict(list)
for _ in range(e):
x,y,k = [int(x) for x in input().split()]
kop[(x-1,y-1)].add(k%10)
kop[(y-1,x-1)].add(10 - (k%10))
gran[x-1].append(y-1)
gran[y-1].append(x-1)
out = [0]*10
founder = [[0]*n for _ in range(10)]
found = [False]*n
for i in range(n):
if found[i]:
continue
que = deque()
que.append((i,0))
cluster = set()
while len(que)>0:
j,col = que.pop()
if founder[col][j]==1:
continue
founder[col][j] = 1
found[j] = True
cluster.add(j)
for k in gran[j]:
for kost in kop[(j,k)]:
que.append((k,(kost+col)%10))
if founder[1][i] == 1:
cycle = 1
for d in range(10):
out[d]+=len(cluster)*(len(cluster)-1)
elif founder[2][i] == 1:
cycle = 2
elif founder[5][i] == 1:
cycle = 5
else:
cycle = 0
firstc = [set() for _ in range(10)]
for node in cluster:
for ind in range(10):
if founder[ind][node]==1:
firstc[ind].add(node)
break
dig = [0]*10
for d1 in range(10):
for d2 in range(10):
if d1 != d2:
dig[(d2-d1)%10] += len(firstc[d1])*len(firstc[d2])
else:
dig[0] += len(firstc[d1])*(len(firstc[d1])-1)
#print(dig,cycle)
if cycle==2:
summaEv = dig[0]+dig[2]+dig[4]+dig[6]+dig[8]
for d in [0,2,4,6,8]:
out[d]+=summaEv
summaOdd = dig[1]+dig[3]+dig[5]+dig[7]+dig[9]
for d in [1,3,5,7,9]:
out[d]+=summaOdd
elif cycle==5:
summa0 = dig[0] + dig[5]
summa1 = dig[1] + dig[6]
summa2 = dig[2] + dig[7]
summa3 = dig[3] + dig[8]
summa4 = dig[4] + dig[9]
for d in [0,5]:
out[d]+=summa0
for d in [1,6]:
out[d]+=summa1
for d in [2,7]:
out[d]+=summa2
for d in [3,8]:
out[d]+=summa3
for d in [4,9]:
out[d]+=summa4
elif cycle==0:
for d in range(10):
out[d] += dig[d]
for d in range(10):
print(out[d])
Python 2 Toll Cost Digits HackerRank Solution
from collections import defaultdict as ddic
from sys import stdin
rr = lambda: stdin.readline().strip()
rrM = lambda: map(int, rr().split())
N,E = rrM()
edges = [rrM() for _ in xrange(E)]
graph = ddic(lambda: ddic(set))
for x,y,w in edges:
x -= 1
y -= 1
w %= 10
graph[x][y].add(w)
graph[y][x].add(-w%10)
ans = [0] * 10
saw = set()
for i in xrange(N):
if i in saw: continue
# for each connected component..
cities = ddic(int)
stack = [(i, 0)]
seen = {(i, 0)}
while stack:
node, residue = stack.pop()
cities[node] |= 1<<residue
for nei, wtset in graph[node].iteritems():
for wt in wtset:
candidate = (nei, (residue+wt)%10)
if candidate not in seen:
seen.add(candidate)
stack.append(candidate)
for node in cities:
saw.add(node)
citiesinv = ddic(int)
for i, u in cities.iteritems():
citiesinv[u] += 1
for b1, c1 in citiesinv.iteritems():
for b2, c2 in citiesinv.iteritems():
#b1 = bitint, c1 = count of cities with that bitint
for d in xrange(10):
if any( (b1 >> i)&1 and (b2 >> ((i+d)%10))&1
for i in xrange(10)):
ans[d] += c1 * c2
if b1 == b2:
ans[d] -= c1
for x in ans: print x
C Toll Cost Digits HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _lnode{
int x;
int w;
struct _lnode *next;
} lnode;
void dfs(int x,int len);
void insert_edge(int x,int y,int w);
int trace[100000],dp[100000],odd,even,five,count;
long long ans[10],temp[10],temp2[10],temp3[10],save1[100000][10],save2[100000][10];
lnode *table[100000];
int main(){
int n,m,x,y,w,i,j;
long long t1,t2;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++){
scanf("%d%d%d",&x,&y,&w);
insert_edge(x-1,y-1,w%10);
}
for(i=0;i<n;i++)
if(!trace[i]){
memset(temp,0,sizeof(temp));
memset(temp2,0,sizeof(temp2));
odd=even=five=count=0;
dfs(i,0);
if(odd || (even && five))
for(j=0;j<10;j++)
ans[j]+=count*(long long)(count-1);
else if(five){
temp[0]*=2;
temp[5]*=2;
for(j=1;j<5;j++)
temp[j]=temp[10-j]=temp[j]+temp[10-j];
for(j=0;j<5;j++)
temp[j]=temp[j+5]=temp[j]+temp[j+5];
for(j=0;j<10;j++)
ans[j]+=temp[j];
}
else if(even){
temp[0]*=2;
temp[5]*=2;
for(j=1;j<5;j++)
temp[j]=temp[10-j]=temp[j]+temp[10-j];
for(j=t1=t2=0;j<10;j++)
if(j%2)
t1+=temp[j];
else
t2+=temp[j];
for(j=0;j<10;j++)
if(j%2)
temp[j]=t1;
else
temp[j]=t2;
for(j=0;j<10;j++)
ans[j]+=temp[j];
}
else{
temp[0]*=2;
temp[5]*=2;
for(j=1;j<5;j++)
temp[j]=temp[10-j]=temp[j]+temp[10-j];
for(j=0;j<10;j++)
ans[j]+=temp[j];
}
}
for(i=0;i<10;i++)
printf("%lld\n",ans[i]);
return 0;
}
void dfs(int x,int len){
int t,i;
lnode *p;
count++;
trace[x]=1;
dp[x]=len;
for(i=0;i<10;i++)
temp[i]+=temp2[i];
temp2[0]++;
memcpy(&save1[x][0],temp2,sizeof(temp2));
for(p=table[x];p;p=p->next)
if(!trace[p->x]){
for(i=0;i<10;i++)
temp3[(i+p->w)%10]=temp2[i];
memcpy(temp2,temp3,sizeof(temp2));
dfs(p->x,(len+p->w)%10);
save2[p->x][0]++;
for(i=0;i<10;i++)
save2[x][(i+p->w)%10]+=save2[p->x][i];
save2[p->x][0]--;
for(i=0;i<10;i++)
temp2[i]=save2[x][(10-i)%10];
for(i=0;i<10;i++)
temp2[i]+=save1[x][i];
}
else{
t=dp[p->x];
t=(10-t+len+p->w)%10;
if(!t);
else if(t==5)
five=1;
else if(t%2)
odd=1;
else
even=1;
}
return;
}
void insert_edge(int x,int y,int w){
lnode *t=malloc(sizeof(lnode));
t->x=y;
t->w=w;
t->next=table[x];
table[x]=t;
t=malloc(sizeof(lnode));
t->x=x;
t->w=(10-w)%10;
t->next=table[y];
table[y]=t;
return;
}
Leave a comment below
