Balanced System File Partition Solution in java
Published: 2022-09-08 10:22:58

## Question

The directory structure of a system disk partition is represented as a tree. Its n directories are numbered from 0 to n-1, where the root directory has the number 0. The structure of the tree is defined by a parent array, where parent[i] = j means that the directory i is a direct subdirectory of j. Since the root directory does not have a parent, it will be represented as a parent[0] = -1. The value in files_size[i] denotes the sum of the sizes in kilobytes of the files located in directory i, but excluding its subdirectories. The size of the content of a directory is defined as the size of all of its subdirectories. Partition the tree into two smaller ones by cutting one branch so that the sizes of the resulting subtrees are as close as possible.

Example parent = [-1,0,0,1,1,2] files_size = [1,2,2,1,1,1]

The structure of the system is shown in the diagram below. The nodes are labeled as /<file_size>. -> Image File

Cut the branches between directories 1 and 0. The partition {0,2,5} has size files_size[0] + files_size[2] + files_size[5] = 1 + 2 + 1 = 4. The partition {1,3,4} has size files_size[1] + files_size[3] + files_size[4] = 2 + 1 + 1 = 4. The absolute difference between the sizes of the two new trees is 4 - 4 = 0. Since no other partition can have a smaller absolute difference, the final answer is 0.

Function Description Complete the function mostBalancedPartition in the editor below.

The function has the following parameter(s): int parent[n]: each parent[i] is the parent directory of directory i int files_size[n]: each file_sizes[i] is the sum of file sizes in directory i

Returns int: the minimum absolute difference in the size of content between two subtrees

Constraints 2 <= n <= 10^5 1 <= files_size[i] <= 10^4 parent[0] = -1 parent[i] < i for 1 <= i < n The depth of each directory tree is at most 500.

Sample Input parent = [-1,0,1,2] files_size = [1,4,3,4] Sample Output 2 Sample Input parent = [-1,0,0,0] files_size = [10,11,10,10] Sample Output 19

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/082urby3g1lxh8de6q4n.png)



## Solution
`
import java.util.*;
public class BalencedFileSystem {

    public static int balencedFile(int[] p,int[] f,int n)
    {
        int[] t = new int[n];
        int cur;
         int temp=0;
        for(int i=0;i<n;i++)
        {
            cur=i;
            while(cur!=-1)
            {
                t[cur]+=f[i];
                cur=p[cur];
            }
        }
        int val = Math.abs(t[0]-2*t[1]);
         for(int i=1;i<n;i++)
         {
            temp = Math.abs(t[0]-2*t[i]);
            if(val>temp)
            {
               val = temp;
            }
         }
         return val;
    }
    
    public static void main(String[] args)
    {
        Scanner sc= new Scanner(System.in);
        System.out.println("enetr the size of array");
        int n=sc.nextInt();
        int[] p= new int[n];
        int[] f = new int[n];
        System.out.println("enetr the parent array");
        for(int i=0;i<n;i++)
        {
            p[i]=sc.nextInt();
        }
        System.out.println("enetr the file size array");
        for(int i=0;i<n;i++)
        {
            f[i]=sc.nextInt();
        }
        int ans = balencedFile(p,f,n);
        System.out.println("ans :" +ans);

        sc.close();
    }
}

`

p is the parent array 
f is the file size array