minimum number of groups of kids with difference of ages between any 2 students is at most 1

Question

I need help with the following code, I am writing a code to minimize the number of groups of the ages of children at a party, that is the difference between the ages of any two children in a group is supposed to be 0/1.

Example:

total number of children = 13

ages of the children = [2,2,2,3,3,3,4,4,4,5,5,6,7]

output:

[2,2,2,3,3,3] - group1
[4,4,4,5,5]- group2 
[6,7] - group3

We don't have to print all three arrays, the number of groups will suffice, kindly check my code and tell me if there is something wrong

public static void main(String[] args) {
        
    Scanner scan = new Scanner(System.in);
    System.out.println("Enter the number of Kids :");
    int n = scan.nextInt();
    int[] kids = new int[n];
    System.out.println("Enter the ages of kids :");
    for(int i = 0;i<n;i++) {
        kids[i] = scan.nextInt();
    }
    Arrays.sort(kids);
    int groups =0;
    int i =0;
    int k =0;
    int a = 0;
    int b =0;
    for(i=a;i<kids.length-a;i++) {
        for(k=b+1;k<kids.length-b;k++) {
            if(kids[k]-kids[i]!=0 || kids[k]-kids[i]!=1) {
                groups++;
                kids[i] = kids[k];
                a++;
                b++;
            }
                
        }
    }
    System.out.println(groups);
}

Is the input array always sorted? – cdaiga Oct 19 '20 at 13:26 — cdaiga, Oct 19 '20 at 13:26

Yash Shah · Accepted Answer · 2020-10-19T13:41:56.403

2

You can do it within O(n*log(n)) time complexity on an average for sorting and in O(n) time complexity for group calculation.

Maintain a variable that contains the current kid's age in a loop. If it exceeds any kid's age increment groups and updates that variable with the current one.

Take a look at the code below to have a better understanding.

public class Main {
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        System.out.println("Enter the number of Kids :");
        int n = scan.nextInt();
        int[] kids = new int[n];
        System.out.println("Enter the ages of kids :");
        for(int i = 0;i<n;i++) {
            kids[i] = scan.nextInt();
        }
        Arrays.sort(kids);
        
        int groups = 1;
        int i = 0;
        int a = kids[i];
        
        for(i=0;i<kids.length;i++) {
            if(kids[i] - a > 1){
                a = kids[i];
                groups = groups + 1;
            }    
        }
        
        System.out.println(groups);
        
        
    }
}

edited Oct 19 '20 at 13:41

answered Oct 19 '20 at 13:21

Yash Shah

1,634
1
5
16

The worst case of Arrays.sort() is O(n2). [Will Arrays.sort() increase time complexity and space time complexity?](https://stackoverflow.com/questions/22571586/will-arrays-sort-increase-time-complexity-and-space-time-complexity) – cdaiga Oct 19 '20 at 13:35
@cdaiga I have updated my answer, Thanks for your valuable comment. – Yash Shah Oct 19 '20 at 13:43
According to the java jvm 8 javadocs of Arrays.sort() method: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations. – Avik Kesari Oct 19 '20 at 14:10
@nadavirinchi If you think that my solution had solved your problem, Could you accept/Upvote it, Please? – Yash Shah Oct 19 '20 at 14:28

score 0 · Answer 2 · answered Oct 19 '20 at 14:03

Sorry for using very layman Java, but I wanted to just demonstrate the logic. If we just need the count of arrays, then this can be done in linear time after sorting, so complexity is O(nlogn) due to sort.

public static void main(String[] args) {

    int[] arr = new int[] { 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6, 7 };
    int maxArrays = 0;
    Arrays.sort(arr);
    int maxLength = removeDuplicates(arr);

    for (int i = 1; i < maxLength; i++) {
        maxArrays++;
        if (arr[i] - arr[i - 1] == 1)
            i++;// shift
    }

    System.out.println(maxArrays);
}

private static int removeDuplicates(int[] arr) {

    int index = 1;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] != arr[i - 1]) {
            arr[index] = arr[i];
            index++;
        }
    }

    return index;
}

Conffusion · Answer 3 · 2020-10-19T14:25:34.957

If you're only interested in the number of groups you can do it in a linear time:

int[] kids= {2,2,2,2,3,3,4,4,5,5,6,7};
Set<Integer> groups=new HashSet<>();

for (int k=0;k<kids.length;k++)
{
    // key is always the even value (2->2, 3->2, 4->4,...)
    int key=kids[k]-kids[k]%2;
    // check on !groups.contains(key) is not necessary as Set.add guarantees no duplicates are added.
    groups.add(key);
}
System.out.println("Number of groups:"+groups.size());

The set contains the even ages wherefor children exist with age key or key+1 in the list. The output for this example is 3.

If you also want to keep the childrens ages in every group, use a HashMap instead of a Set:

HashMap<Integer,List<Integer>> groups;

in which key is the even age (as in the set) and the value is a list of children's ages.

minimum number of groups of kids with difference of ages between any 2 students is at most 1

3 Answers3