Easy Explanation || JAVA || Bit Manipulation || Union Find || beats 100%
ProblemRequirement is to find the path having minimum cost among all paths connecting a vertex u with a vertex v. Cost of a path is the bitwise AND of all edge
![Screenshot 2025-03-21 011629.png](https://assets.leetcode.com/users/images/fcc5b51a-25b1-47a8-bc57-a74c73b957e8_1742500044.9909396.png)


<!-- Describe your first thoughts on how to solve this problem. -->
# Problem

Requirement is to find the path having minimum cost among all paths connecting a vertex u with a vertex v. Cost of a path is the bitwise AND of all edge weights that are present along this path. If there is no path between vertex u and vertex v, then the cost should be -1. A path can be used multiple times. 

# Intuition

Bitwise AND of any set of values either stay same or decreases. So the bitwise AND of all weights will always be lesser than any subset of weights.

So all vertices having connections with each other can be grouped and the bitwise AND of weights of all edges in that group can be calculated to find the minimum value. 

To group the vertices based on edges, Union Find Algorithm can be used and while connecting the vertices to same group, Bitwise AND value of the group can be updated. 

At the start, set the Bitwise AND value of a group to Integer.MAX_VALUE(31 1's). The Bitwise AND of Integer.MAX_VALUE with any number x is x. As edges are added to group, update the group value.

If the vertices are not in same group return -1.

# Complexity
- Time complexity:  O(V+E+M)

V -> number of vertices
E -> number of edges
M -> number of queries

<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(V)

V -> number of vertices
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    
    // Union Find Algorithm
    class DSU{

        int[] parent;
        int[] size;
        int[] groupVal;

        //  Initiate and add edges to group
        DSU(int n,int[][] edges){
            parent=new int[n];
            size=new int[n];
            groupVal=new int[n];

            // TC: O(V)
            for(int i=0;i<n;i++){
                parent[i]=i;
                size[i]=1;
                groupVal[i]=Integer.MAX_VALUE;
            }

            // TC: O(E)
            for(int[] edge:edges){
                union(edge[0],edge[1],edge[2]);
            }
        }

        // TC: O(alpha) similar to O(constant) 
        public int findParent(int u){
            if(u==parent[u]) return u;
            return parent[u]=findParent(parent[u]);
        }

        // TC: O(constant)
        public void union(int u,int v,int w){
            int pu=findParent(u);
            int pv=findParent(v);
            int master=pu,slave=pv;

            if(master==slave){
                groupVal[master]=groupVal[master]&w;
            }

            if(size[pv]>size[pu]){
                master=pv;
                slave=pu;
            }


            parent[slave]=master;
            size[master]+=size[slave];
            groupVal[master]=groupVal[master]&groupVal[slave]&w;
        }

        // TC: O(constant)
        public int getCost(int u,int v){
            int pu=findParent(u);
            int pv=findParent(v);
            if(pu!=pv) return -1;
            return groupVal[pu];
        }
    }


    public int[] minimumCost(int n, int[][] edges, int[][] query) {
        int m=query.length;
        int[] res=new int[m];
        DSU unionObj=new DSU(n,edges);

        // TC: O(M)
        for(int i=0;i<m;i++){
            res[i]=unionObj.getCost(query[i][0],query[i][1]);
        }
        return res;
    }
}
```
['Bit Manipulation', 'Union Find', 'Java']