HackerRank Black and White Tree problem solution YASH PAL, 31 July 202425 January 2026 In this HackerRank Black and White Tree problem solution Nikita is making a graph as a birthday gift for her boyfriend, a fellow programmer! She drew an undirected connected graph with N nodes numbered from 1 to N in her notebook.Each node is shaded in either white or black. We define nW to be the number of white nodes, and nB to be the number of black nodes. The graph is drawn in such a way that:No 2 adjacent nodes have same coloring.The value of |nW – nB|, which we’ll call D, is minimal.Nikita’s mischievous little brother erased some of the edges and all of the coloring from her graph! As a result, the graph is now decomposed into one or more components. Because you’re her best friend, you’ve decided to help her reconstruct the graph by adding K edges such that the aforementioned graph properties hold true.Given the decomposed graph, construct and shade a valid connected graph such that the difference |nW – nB| between its shaded nodes is minimal.HackerRank Black and White Tree problem solution in Java.import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import java.util.Stack; public class BlackAndWhiteTree { static final List<Graph> graphs = new ArrayList<>(); static int ones = 0; static int zeroes = 0; public static void main(String[] args) throws Exception { try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) { String[] line = br.readLine().split(" "); Node[] nodes = new Node[Integer.parseInt(line[0])]; for (int e = 0; e < nodes.length; e++) { nodes[e] = new Node(e); } for (int e = Integer.parseInt(line[1]); e > 0; e--) { line = br.readLine().split(" "); nodes[Integer.parseInt(line[0]) - 1].adjacent.add(nodes[Integer.parseInt(line[1]) - 1]); nodes[Integer.parseInt(line[1]) - 1].adjacent.add(nodes[Integer.parseInt(line[0]) - 1]); } int components = 0; for (int e = 0; e < nodes.length; e++) if (!nodes[e].visited) { Graph g = new Graph(nodes[e]); if (g.diffs == 0) { zeroes++; } else if (g.diffs == 1) { ones++; } else { components += g.diffs; } graphs.add(g); } Collections.sort(graphs, (g1, g2) -> Math.abs(g1.diffs) - Math.abs(g2.diffs)); final int SIZE = components / 2 + 1; boolean[] dinam = new boolean[SIZE]; int[] parent = new int[SIZE]; Arrays.fill(parent, Integer.MAX_VALUE); dinam[0] = true; int lastMax = 0; for (int g = ones + zeroes; g < graphs.size(); g++) { final int dif = graphs.get(g).diffs, top = Math.min(SIZE, lastMax + dif + 1); for (int e = top - 1; e >= dif; e--) { dinam[e] |= dinam[e - dif]; if (dinam[e - dif]) { parent[e] = Math.min(parent[e], dif); } } lastMax += dif; } int min = 0; int mindiff = components; for (int e = 0; e < SIZE; e++) if (dinam[e] && calcMin(Math.abs(components - 2 * e)) < calcMin(Math.abs(components - 2 * min))) { min = e; mindiff = Math.abs(components - 2 * e); } final int minValue = calcMin(Math.abs(components - 2 * min)); for (int g = graphs.size() - 1; g >= 0; g--) { if (graphs.get(g).diffs == 0) { } else if (graphs.get(g).diffs == 1) { graphs.get(g).signum = g < zeroes + mindiff || (g % 2) == 1; } else if (min > 0 && parent[min] == graphs.get(g).diffs) { graphs.get(g).signum = true; min -= graphs.get(g).diffs; } } Collections.sort(graphs, (g1, g2) -> Boolean.compare(g1.signum, g2.signum)); Graph root = graphs.get(graphs.size() - 1); System.out.println(minValue + " " + (graphs.size() - 1)); for (int g = 0; g < graphs.size() - 1; g++) { if (graphs.get(g).signum == root.signum) { root.root.adjacent.get(0).adjacent.add(graphs.get(g).root); graphs.get(g).root.adjacent.add(root.root.adjacent.get(0)); System.out.println(root.root.adjacent.get(0).id + " " + graphs.get(g).root.id); } else { root.root.adjacent.add(graphs.get(g).root); graphs.get(g).root.adjacent.add(root.root); System.out.println(root.root.id + " " + graphs.get(g).root.id); } } } } public static int calcMin(int x) { if (ones < x) { return x - ones; } return (ones - x) % 2; } static class Graph { Node root; int whites, blacks, diffs, size; boolean signum = false; public Graph(Node root) { this.root = root; Stack<Node> n = new Stack<>(); n.add(root); while (!n.isEmpty()) { Node next = n.pop(); if (next.visited) continue; next.parent = root.parent; next.visited = true; if (next.isWhite) { whites++; } else { blacks++; } for (Node e : next.adjacent) { e.isWhite = !next.isWhite; n.push(e); } } diffs = blacks - whites; size = blacks + whites; if (blacks - whites < 0) { invert(); } } public void invert() { root = root.adjacent.get(0); int t = blacks; blacks = whites; whites = t; diffs = blacks - whites; size = blacks + whites; } } static class Node { int parent, id; boolean isWhite, visited; ArrayList<Node> adjacent = new ArrayList<>(); public Node(int parent) { this.parent = parent; this.id = parent + 1; } } } Black and White Tree problem solution in C++.#include <bits/stdc++.h> using namespace std; #define ft first #define sd second #define pb push_back #define all(x) x.begin(),x.end() #define ll long long int #define vi vector<int> #define vii vector<pair<int,int> > #define pii pair<int,int> #define vl vector<ll> #define vll vector<pair<ll,ll> > #define pll pair<ll,ll> #define pli pair<ll,int> #define mp make_pair #define sc1(x) scanf("%d",&x) #define sc2(x,y) scanf("%d%d",&x,&y) #define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define scll1(x) scanf("%lld",&x) #define scll2(x,y) scanf("%lld%lld",&x,&y) #define scll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z) #define pr1(x) printf("%dn",x) #define pr2(x,y) printf("%d %dn",x,y) #define pr3(x,y,z) printf("%d %d %dn",x,y,z) #define prll1(x) printf("%lldn",x) #define prll2(x,y) printf("%lld %lldn",x,y) #define prll3(x,y,z) printf("%lld %lld %lldn",x,y,z) #define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ; #define f_in(st) freopen(st,"r",stdin) #define f_out(st) freopen(st,"w",stdout) #define fr(i, a, b) for(i=a; i<=b; i++) #define fb(i, a, b) for(i=a; i>=b; i--) #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> const int maxn = 1e5 + 10; const int mod = 1e9 + 7; const int N=200010; int w[2]; vector <int> v[N]; int a[N], d[N], p[N], c[N], col[N], sz, ccol[2][N]; bool f[N]; queue<int> q[N]; void dfs(int x,int y) { f[x]=1; w[y]++; col[x] = y; ccol[y][sz] = x; for (int i=0;i<v[x].size();i++) if (!f[v[x][i]]) dfs(v[x][i],(y^1)); else if( col[v[x][i]] != 1 - y ) assert(0); } int main() { int n,m; scanf("%d%d",&n,&m); for (int i=0,x,y;i<m;i++) { scanf("%d%d",&x,&y); v[x].push_back(y); v[y].push_back(x); } int k=0; for (int i=1;i<=n;i++) { if (!f[i]) { w[0] = w[1]=0; dfs(i,0); c[i] = (w[0] < w[1]); k+=abs(w[0]-w[1]); a[abs(w[0]-w[1])]++; q[abs(w[0]-w[1])].push( i ); } } for (int j=1;j<=k;j++) d[j]=N; for (int i=1;i<=n;i++) { if (a[i]) { for (int j=0;j+i<=k;j++) { if( d[i+j] == N && d[j] != N ) { d[i+j] = d[j] + 1; p[i+j] = j; } } for (int j=1;j<=k;j++) { if (d[j]>a[i]) { d[j]=N; p[j]=0; } else { d[j]=0; } } } } int ans=k, v = 0; for (int i=0;i<=k;i++) { if(d[i]<N) { if( ans >= abs(k - 2 * i) ) { ans = abs(k - 2 * i); v = i; } } } memset(f, 0, sizeof f); while( v != 0 ) { int diff = v - p[v]; int nd = q[diff].front(); q[diff].pop(); sz ++; dfs(nd, c[nd]); v = p[v]; } for(int i=1; i<=n; i++) { if( !f[i] ) { sz ++; dfs(i, 1 - c[i]); } } int blk, wht, idb, idw; blk = wht = idb = idw = -1; for(int i=1; i<=sz; i++) { if( ccol[0][i] ) { blk = ccol[0][i]; idb = i; } if( ccol[1][i] ) { wht = ccol[1][i]; idw = i; } } cout << ans << " " << sz - 1 << "n"; if( idb != idw ) cout << blk << " " << wht << "n"; for(int i=1; i<=sz; i++) { if( i != idb && i != idw ) { if( ccol[0][i] ) { cout << wht << " " << ccol[0][i] << "n"; } else { cout << blk << " " << ccol[1][i] << "n"; } } } return 0; } Problem solution in C.#include <stdio.h> #include <stdlib.h> #include <string.h> #define HASH_SIZE 1234555 typedef struct _node{ int t; int i; int c; int a; struct _node *next; } node; typedef struct _lnode{ int x; int w; struct _lnode *next; } lnode; int abss(int x); void insert_edge(int x,int y,int w); void dfs(int x,int c); void sort_a2(int*a,int*b,int size); void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size); void sort_a_ad(int*a,int*c,int size,int*new_size); void merge_ad(int*a,int*left_a,int*right_a,int*c,int*left_c,int*right_c,int left_size, int right_size,int*new_size); void insert(int target,int idx,int c,int a); int search(int target,int idx,int *c); int solve(int target,int target2,int idx); void clean_table(); int N,w,b,ngs,*cans,*cdiff,*c,idx[200000],*trace,mark[200000]={0},diff[200000],f[200000],s[200000],*remain; lnode **table; node *hash[HASH_SIZE]={0}; int main(){ int M,x,y,gs,sum,ans,target,i,j,k; scanf("%d%d",&N,&M); table=(lnode**)malloc(N*sizeof(lnode*)); memset(table,0,N*sizeof(lnode*)); for(i=0;i<M;i++){ scanf("%d%d",&x,&y); insert_edge(x-1,y-1,1); } trace=(int*)malloc(N*sizeof(int)); memset(trace,0,N*sizeof(int)); for(i=gs=0;i<N;i++) if(!trace[i]){ w=b=0; dfs(i,0); x=i; if(table[i]) y=table[i]->x; else y=-1; if(w>b){ diff[gs]=w-b; f[gs]=x; s[gs]=y; } else{ diff[gs]=b-w; f[gs]=y; s[gs]=x; } idx[gs]=gs; gs++; } free(trace); clean_table(); free(table); cdiff=(int*)malloc(gs*sizeof(int)); c=(int*)malloc(gs*sizeof(int)); for(i=sum=0,ans=200001;i<gs;i++){ sum+=diff[i]; cdiff[i]=diff[i]; c[i]=1; } target=sum/2; sort_a2(diff,idx,gs); sort_a_ad(cdiff,c,gs,&ngs); remain=(int*)malloc(ngs*sizeof(int)); if(!M || ngs==1){ printf("%d %dn",gs%2*cdiff[0],gs-1); for(i=0;i<gs-1;i++) printf("%d %dn",f[i]+1,f[i+1]+1); return 0; } for(i=0;i<ngs;i++) if(i==0) remain[i]=c[i]*cdiff[i]; else remain[i]=remain[i-1]+c[i]*cdiff[i]; ans=solve(target,(sum+1)/2,ngs-1); cans=remain; memset(cans,0,ngs*sizeof(int)); for(i=ngs-1;i>=0;i--){ if(target<=0) break; if(i==0){ cans[i]=(target-1)/cdiff[i]+1; break; } search(target,i,&cans[i]); if(cans[i]==-1){ for(j=i;j>=0;j--) cans[j]=c[j]; break; } target-=cans[i]*cdiff[i]; } for(j=0,k=0;j<gs && k<ngs;k++){ x=j+cans[k]; for(;j<x;j++) mark[j]=1; while(diff[j]==cdiff[k] && j<gs) j++; } printf("%d %dn",abss(2*ans-sum),gs-1); for(i=0;i<gs;i++) if(s[idx[i]]!=-1) k=i; for(i=0;i<gs;i++){ if(i==k) continue; if(mark[i]!=mark[k]) printf("%d %dn",f[idx[i]]+1,f[idx[k]]+1); else printf("%d %dn",f[idx[i]]+1,s[idx[k]]+1); } return 0; } int abss(int x){ return (x<0)?-x:x; } 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=w; t->next=table[y]; table[y]=t; return; } void dfs(int x,int c){ lnode *p; trace[x]=1; if(c) b++; else w++; for(p=table[x];p;p=p->next) if(!trace[p->x]) dfs(p->x,c^1); return; } void sort_a2(int*a,int*b,int size){ if (size < 2) return; int m = (size+1)/2,i; int*left_a,*left_b,*right_a,*right_b; left_a=(int*)malloc(m*sizeof(int)); right_a=(int*)malloc((size-m)*sizeof(int)); left_b=(int*)malloc(m*sizeof(int)); right_b=(int*)malloc((size-m)*sizeof(int)); for(i=0;i<m;i++){ left_a[i]=a[i]; left_b[i]=b[i]; } for(i=0;i<size-m;i++){ right_a[i]=a[i+m]; right_b[i]=b[i+m]; } sort_a2(left_a,left_b,m); sort_a2(right_a,right_b,size-m); merge2(a,left_a,right_a,b,left_b,right_b,m,size-m); free(left_a); free(right_a); free(left_b); free(right_b); return; } void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){ int i = 0, j = 0; while (i < left_size|| j < right_size) { if (i == left_size) { a[i+j] = right_a[j]; b[i+j] = right_b[j]; j++; } else if (j == right_size) { a[i+j] = left_a[i]; b[i+j] = left_b[i]; i++; } else if (left_a[i] <= right_a[j]) { a[i+j] = left_a[i]; b[i+j] = left_b[i]; i++; } else { a[i+j] = right_a[j]; b[i+j] = right_b[j]; j++; } } return; } void sort_a_ad(int*a,int*c,int size,int*new_size){ if (size < 2){ (*new_size)=size; return; } int m = (size+1)/2,i; int *left_a,*right_a,*left_c,*right_c; left_a=(int*)malloc(m*sizeof(int)); right_a=(int*)malloc((size-m)*sizeof(int)); left_c=(int*)malloc(m*sizeof(int)); right_c=(int*)malloc((size-m)*sizeof(int)); for(i=0;i<m;i++){ left_a[i]=a[i]; left_c[i]=c[i]; } for(i=0;i<size-m;i++){ right_a[i]=a[i+m]; right_c[i]=c[i+m]; } int new_l_size=0,new_r_size=0; sort_a_ad(left_a,left_c,m,&new_l_size); sort_a_ad(right_a,right_c,size-m,&new_r_size); merge_ad(a,left_a,right_a,c,left_c,right_c,new_l_size,new_r_size,new_size); free(left_a); free(right_a); free(left_c); free(right_c); return; } void merge_ad(int*a,int*left_a,int*right_a,int*c,int*left_c,int*right_c,int left_size, int right_size,int*new_size){ int i = 0, j = 0,index=0; while (i < left_size|| j < right_size) { if (i == left_size) { c[index] = right_c[j]; a[index++] = right_a[j]; j++; } else if (j == right_size) { c[index] = left_c[i]; a[index++] = left_a[i]; i++; } else if (left_a[i] <= right_a[j]) { c[index] = left_c[i]; a[index++] = left_a[i]; i++; } else { c[index] = right_c[j]; a[index++] = right_a[j]; j++; } if(index>1&&a[index-2]==a[index-1]){ c[index-2]+=c[index-1]; index--; } } (*new_size)=index; return; } void insert(int target,int idx,int c,int a){ int bucket=(target*200000LL+idx)%HASH_SIZE; node *t; t=(node*)malloc(sizeof(node)); t->t=target; t->i=idx; t->c=c; t->a=a; t->next=hash[bucket]; hash[bucket]=t; return; } int search(int target,int idx,int *c){ int bucket=(target*200000LL+idx)%HASH_SIZE; node *t=hash[bucket]; while(t){ if(t->t==target && t->i==idx){ *c=t->c; return t->a; } t=t->next; } return -1; } int solve(int target,int target2,int idx){ if(target<=0) return 0; if(target>remain[idx]) return -1; if(target==remain[idx]){ insert(target,idx,-1,target); return target; } int t,ans=200000,ansc,i; if(idx==0){ t=(target-1)/cdiff[idx]+1; return t*cdiff[idx]; } t=search(target,idx,&w); if(t!=-1) return t; for(i=0;i<=c[idx];i++){ t=solve(target-i*cdiff[idx],target2-i*cdiff[idx],idx-1); if(t!=-1){ if(t+i*cdiff[idx]<ans){ ans=t+i*cdiff[idx]; ansc=i; } if(t+i*cdiff[idx]==target || t+i*cdiff[idx]==target2){ insert(target,idx,i,t+i*cdiff[idx]); return t+i*cdiff[idx]; } } if(target-i*cdiff[idx]<=0) break; } insert(target,idx,ansc,ans); return ans; } void clean_table(){ int i; lnode *p,*pp; for(i=0;i<N;i++) if(table[i]){ p=table[i]; while(p){ pp=p->next; free(p); p=pp; } table[i]=NULL; } return; } Algorithms coding problems solutions AlgorithmsHackerRank