# Cost Evaluation
###### tags: `Union Find`, `Amazon OA`

Description:
A conpany owns N warehouses, identified as warehouse `0` to `n-1`. The owner would like to measure the maintenance cost. A warehouse will be able to share with stock with other connected warehouses, making it less costly to restock.

The method to evaluate the maintenance cost is:
1. If a warehouses are connected, the total maintenance cost is 1.
2. If multiple warehouses to any connected, the total maintenance cost of the group of connected warehouses will be the ceiling of the square root of `k`, where `k` is the number of the warehouses in the group.
3. A warehouse connected to any of the warehouse in the group will be able to share stock with all in the group. For example, if warehouse 0 and warehouse 1 are connted and warehouse 1 and warehouse 2 are connected, consider 0, 1, and 2 in the same group.

Given the number of warehouse `n` and a 2d array `connections`, where every subarray is a pair of connected warehouses, build a function that return the total maintenance cost.

* **Example**

Input
n = 4
connections = [[0, 2], [1, 2]]

Output
3

Explanation:
/warerhouses 0, 1, 2 are in the same group, the cost is ceiling(sqrt(3)) = 2. Warehouse costs 1.
Total cost = 2 + 1 = 3.

Solution:

public class StorageOptimization {
    public int StorageOptimization(int n, int[][] connections) {
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        for (int[] connection: connections) {
            int a = connection[0];
            int b = connection[1];
            union(a, b, parent);
        }

        int total = 0;

        for (int cost: parent) {
            if (cost < 0) total += Math.ceil(Math.sqrt(-cost));
        }
        return total;
    }

    private void union(int a, int b, int[] parent) {
        int parentA = find(a, parent);
        int parentB = find(b, parent);
        if (parentA == parentB) return;

        if (parent[parentA] < parent[parentB]) {
            parent[parentA] += parent[parentB];
            parent[parentB] = parentA;
        } else {
            parent[parentB] += parent[parentA];
            parent[parentA] = parentB;
        }

    }

    private int find(int n, int[] parent) {
        while (parent[n] >= 0) {
            n = find(parent[n], parent);
        }
        return n;
    }
}