(UVA) Vito's Family - Solution 2

If you want to see another solution for this problem, click here.

I used Brute Force to solve this problem.

Considering only the streets where Vito's relatives live, I try all the possibilities to discover the optimal Vito's house.

In this solution, each case takes O(N^2) time to execute while the previous solution takes only O(N), where N is the number of relatives and 0 < N < 500, which makes Solution 2 worse than Solution 1.


import java.io.*;
import java.util.*;

class Main {
    public static void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      
        int numCases = Integer.parseInt(br.readLine());
        for (int i = 0; i < numCases; i++) {
            String line = br.readLine();
            String[] s = line.split("\\s");
            int numRelatives = Integer.parseInt(s[0]);
          
            int[] streetHouses = new int[numRelatives];
            for (int j = 0; j < numRelatives; j++) {
                streetHouses[j] = Integer.parseInt(s[j+1]);
            }         
          
            Arrays.sort(streetHouses);
          
            int sum = 0;
            int minDistance = 2000000000;
            for (int j = 0; j < numRelatives; j++) {
                for (int k = 0; k < numRelatives; k++) {
                    sum += Math.abs(streetHouses[j]-streetHouses[k]);
                }
               
                if (sum < minDistance) {
                    minDistance = sum;
                }
               
                sum = 0;
            }
                                
            bw.write(minDistance + "\n");
        }
      
        bw.flush();
        bw.close();
                              
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
      
        System.exit(0);
    }
}