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

user_10821323 0
Viewed 949

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);
}
data-structures algorithm java
3 Answers

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);
        
        
    }
}
user_136519780

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;
}
user_113526720

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.

user_36596700
Related