Shortest path length between two given nodes such that adjacent nodes are at bit difference 2 | C ++ program for the above approach ; Function to count set bits in a number ; Stores count of set bits in xo ; Iterate over each bits of xo ; If current bit of xo is 1 ; Update count ; Update xo ; Function to find length of shortest path between the nodes a and b ; Stores XOR of a and b ; Stores the count of set bits in xorVal ; If cnt is an even number ; Driver Code ; Given N ; Given a and b ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countbitdiff ( int xo ) { int count = 0 ; while ( xo ) { if ( xo % 2 == 1 ) { count ++ ; } xo = xo / 2 ; } return count ; } void shortestPath ( int n , int a , int b ) { int xorVal = a ^ b ; int cnt = countbitdiff ( xorVal ) ; if ( cnt % 2 == 0 ) cout << cnt / 2 << endl ; else cout << " - 1" << endl ; } int main ( ) { int n = 15 ; int a = 15 , b = 3 ; shortestPath ( n , a , b ) ; return 0 ; }