CODEWITHSUNDEEP
c++bitbitmask
Ujjwal.Maurya0619
Ujjwal.Maurya0619

Reputation: 25

Given solution using Bitmask, I am unable to understand the evaluation of condition as marked in code

I an unable to understand the bit masking used here, the given code is a solution of finding no of palindrome paths in a binary tree which contains digits 0-9 inclusive. I have marked the line in code with in a if statement.

This is the question of LeetCode contest. Question is as given:

Pseudo-Palindromic Paths in a Binary Tree, Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

    int pseudoPalindromicPaths (TreeNode* root) {
        return dfs(root, 0);
    }

    int dfs(TreeNode* root, int count) {
        if (!root) return 0;
        count ^= 1 << (root->val - 1);
        int res = dfs(root->left, count) + dfs(root->right, count);
        if (root->left == root->right && (count & (count - 1)) == 0) res++;
        //--------------------------------------^--THIS SECTION-----
        count ^= 1 << (root->val - 1);
        return res;
    }

Upvotes: 0

Views: 149

Answers (2)

Arya A.
Arya A.

Reputation: 22

class Solution {
    public int traverse(TreeNode root, int numNode, int[] arr){
        arr[(root.val-1)]+=1;
        
        int path = 0;
        if(root.left!=null)
            path+=traverse(root.left, numNode+1, arr);
        
        if(root.right!=null)
            path+=traverse(root.right, numNode+1, arr);
        
        if((root.left==null)&&(root.right==null)){
            if((numNode%2)==0){
                boolean flag = true;
                for(int i: arr){
                    if((i%2)==1){
                        flag = false;
                        break;
                    }
                }
                if(flag)
                    path+=1;
            }
            else{
                int numOdd = 0;
                for(int i: arr)
                    if((i%2)==1)
                        numOdd++;
                if(numOdd==1)
                    path+=1;
            }
        }
        
        arr[root.val-1]-=1;
        return path;
    }
    public int pseudoPalindromicPaths (TreeNode root) {
        return traverse(root, 1, new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0});
    }
}

Upvotes: 0

Tony Tannous
Tony Tannous

Reputation: 14863

count & (count - 1) == 0

If count is a power of 2, this statement is true.

Example: Count = 8

00001000 = 8
&
00000111 = (8-1) = 7 
------------
00000000 = 0

Upvotes: 1

Related Questions