Question

You are given an array of arrays a. Your task is to group the arrays a[i] by their mean values, so that arrays with equal mean values are in the same group, and arrays with different mean values are in different groups.

Each group should contain a set of indices (i, j, etc), such that the corresponding arrays (a[i], a[j], etc) all have the same mean. Return the set of groups as an array of arrays, where the indices within each group are sorted in ascending order, and the groups are sorted in ascending order of their minimum element.

Example

• For

• a = [[3, 3, 4, 2],
•      [4, 4],
•      [4, 0, 3, 3],
•      [2, 3],
•      [3, 3, 3]]

the output should be

meanGroups(a) = [[0, 4],

                 [1],

                 [2, 3]]

• mean(a[0]) = (3 + 3 + 4 + 2) / 4 = 3;
• mean(a[1]) = (4 + 4) / 2 = 4;
• mean(a[2]) = (4 + 0 + 3 + 3) / 4 = 2.5;
• mean(a[3]) = (2 + 3) / 2 = 2.5;
• mean(a[4]) = (3 + 3 + 3) / 3 = 3.

There are three groups of means: those with mean 2.5, 3, and 4. And they form the following groups:

• Arrays with indices 0and 4 form a group with mean 3;
• Array with index 1 forms a group with mean 4;
• Arrays with indices 2and 3 form a group with mean 2.5.

Note that neither

meanGroups(a) = [[0, 4],

                 [2, 3],

                 [1]]

nor

meanGroups(a) = [[0, 4],

                 [1],

                 [3, 2]]

will be considered as a correct answer:

• • In the first case, the minimal element in the array at index 2 is 1, and it is less then the minimal element in the array at index 1, which is 2.
  • In the second case, the array at index 2 is not sorted in ascending order.
• For

• a = [[-5, 2, 3],
•      [0, 0],
•      [0],
•      [-100, 100]]

the output should be

meanGroups(a) = [[0, 1, 2, 3]]

The mean values of all of the arrays are 0, so all of them are in the same group.

Input/Output

• [execution time limit] 3 seconds (java)
• [input] array.array.integer a

An array of arrays of integers.

Guaranteed constraints:
1 ≤ a.length ≤ 100,
1 ≤ a[i].length ≤ 100,
-100 ≤ a[i][j] ≤ 100.

• [output] array.array.integer

An array of arrays, representing the groups of indices

Answer 1

Code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Mean {
  
   static public void main(String args[])
   {
       // Initializing variables
       int[][] a = new int[100][100]; // Array of arrays for holding the inputs
       Map<Integer,ArrayList<Integer>> averagemaps = new HashMap<Integer,ArrayList<Integer>>(); // Map to contain the average and the list of array indexes
       List<Integer> averages = new ArrayList<Integer>(); // List of averages of the arrays
       Scanner sc = new Scanner(System.in);
      
       // Input for the array of arrays
       System.out.println("Enter the number of arrays: ");
       int noArrays = sc.nextInt();
      
       for(int i = 0; i < noArrays; i++)
       {
           System.out.println("Enter the number of elements in the array "+i+":");
           int noElements = sc.nextInt();
           int sum = 0;
           int avg = 0;
           System.out.println("Enter the elements of the array "+i+" one by one:");
           for(int j = 0; j < noElements; j++)
           {
               a[i][j] = sc.nextInt(); // Input for each elements in the array.
               sum += a[i][j];   // Calculating the sum of the elements in the array.
           }
          
           avg = sum/noElements; // calculating average for the array
          
           // checking if the average is inside the list or not
           if(!averages.contains(avg))
           {  
               // If the average is not already in the list
               // Adding the average into the list
               averages.add(avg);
               // create an array list to
               // hold the list of indices which has the same array
               ArrayList<Integer> a1 = new ArrayList<Integer>();
               a1.add(i);
               // Mapping the average to the list of indices.
               averagemaps.put(avg, a1);
           }
           else
           {
               // The average is present in the list
               // Adding the index to the array list
               // mapped to it.
               averagemaps.get(avg).add(i);
           }
       }
      
       // Sorting the index arrays for each average
       // in ascending order
       Iterator itr=averages.iterator();
       int index = 0;
       while(itr.hasNext()){
              Collections.sort(averagemaps.get(itr.next()));
       }
      
       // For sorting the array of indices based on their lowest number
       // Since the arrays are in a map, the map needs to be sorted.
       // There is no function to sort the map, Hence the map is converted to
       // a list of entersets.
        List<Map.Entry<Integer,ArrayList<Integer>>> list =
                new LinkedList<Map.Entry<Integer,ArrayList<Integer>>>(averagemaps.entrySet());

        // Using the sort function to sort the list. The list should be sorted based on the minimum
        // element in each array.
        Collections.sort(list, new Comparator<Map.Entry<Integer,ArrayList<Integer>>>() {
            public int compare(Map.Entry<Integer,ArrayList<Integer>> o1,
                               Map.Entry<Integer,ArrayList<Integer>> o2) {
               // since the elements in the arrays are already sorted
               // the element in the index 0 will be the smallest element
                return (o1.getValue().get(0)).compareTo(o2.getValue().get(0));
            }
        });

        // Converting the list back to a hashmap
        averagemaps = new HashMap<Integer,ArrayList<Integer>>();
        for (Map.Entry<Integer,ArrayList<Integer>> entry : list) {
           averagemaps.put(entry.getKey(), entry.getValue());
        }
      
        // Initializing an array of array for the output
        // The outer array dimension is defined.
        // The inner array dimension can be defined based on the
        // size of the indices array
       int[][] answer = new int[averages.size()][];
      
       itr = averages.iterator();
      
       // Iterate through the averages lists
       while(itr.hasNext())
       {
           ArrayList<Integer> i = averagemaps.get(itr.next());
           Iterator iterr=i.iterator();
           answer[index] = new int[i.size()];
           int innerindex = 0;
           while(iterr.hasNext())
               answer[index][innerindex++] = (Integer)iterr.next(); // adding the array of indices into the output array.
           index++;
       }
      
       // Printing the arrays of arrays.
       System.out.print("[ ");
       for(int i = 0; i < answer.length; i++)
       {
           System.out.print("[ ");
           for(int j = 0;j < answer[i].length; j++)
               System.out.print(answer[i][j]+ ", ");
           System.out.println("]");
       }
       System.out.println("]");
   }
}

Output:

Enter the number of arrays:
4
Enter the number of elements in the array 0:
3
Enter the elements of the array 0 one by one:
-5
2
3
Enter the number of elements in the array 1:
2
Enter the elements of the array 1 one by one:
0
0
Enter the number of elements in the array 2:
1
Enter the elements of the array 2 one by one:
0
Enter the number of elements in the array 3:
2
Enter the elements of the array 3 one by one:
-100
100
[ [ 0, 1, 2, 3, ]
]