“This is the third day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Count the number of occurrences of each number, and then find out whether there is a common divisor between the numbers

— Leetcode

preface

Hello, I’m One, welcome to my algorithm channel.

Only do interesting algorithms, only write algorithms for interviews.

Question

914. Grouping of cards

Difficulty: Easy

Given a deck of cards, each card has an integer written on it.

At this point, you need to select a number X, so that we can divide the whole deck into 1 or more groups according to the following rules:

Each group has X cards. All the cards in the group have the same integer written on them. Return true only if your optional X >= 2.

Example:

,2,3,4,4,3,2,1 input: [1] output: true explanation: feasible grouping is [1, 1], [2], [3], [4]Copy the code

Solution

The success of grouping depends on the number of occurrences of each array. Is the number of occurrences of each number the same?

not

As long as there’s a common divisor. If one has two, and two has four, that’s fine.

So the problem becomes finding common divisor. It’s a math problem

Seeking common divisor I believe you have learned to go to school division, also known as Euclid algorithm, that how to use the program to achieve it?

Be sure to keep this template in mind.

    // Toss and turn division
    private int gcd (int a, int b) {
        return b == 0? a: gcd(b, a % b);
    }
Copy the code

Code counting method is also worth learning, skillfully use the array to count, than the use of Map concise many.

Anyway, this one needs to be memorized.

Code

/ * * *@authorA coding * /
class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        / / count
        int[] counter = new int[10000];
        for (int num: deck) {
            counter[num]++;
        }
        / / the GCD
        int x = 0;
        for(int cnt: counter) {
            if (cnt > 0) {
                x = gcd(x, cnt); 
                if (x == 1) { 
                    return false; }}}return x >= 2;
    }
    
    // Toss and turn division
    private int gcd (int a, int b) {
        return b == 0? a: gcd(b, a % b); }}Copy the code

The last

Thumbs up, thumbs up, and fucking thumbs up!