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

The title

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:

  • In each groupXCARDS.
  • All the cards in the group have the same integer written on them.

Return true only if your optional X >= 2.

Example 1:

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

Example 2:

Input: deck = [1,1,1,2,2,2,3,3] output: false description: there is no grouping that satisfies the requirement.Copy the code

Tip:

  • 1 <= deck.length <= 10^4
  • 0 <= deck[i] < 10^4

thinking

This is an interesting problem.

We divide the cards into groups. Each group needs to be the same. For example, [1,2,3,3,2,1] can be divided into groups [1,1], [2,2], [3,3].

Also, we noticed that we could divide into many of the same groups. Such as,1,1,1,2,2,3,3 [1] can be divided into [1, 1], [1, 1], [2], [3, 3] four groups, and,1,1,2,2,2,3,3 [1] cannot grouping. The number of cards in each group must be x >= 2. We can find that the number of cards in each group is the maximum common divisor of the number of all kinds of cards, which is required to meet the condition of >= 2 in the question.

So, we can count each card first, and then, find its greatest common divisor, and then determine whether it meets the condition of x >= 2.

We can find the greatest common divisor of two numbers by means of toss and turn division. So you compute the remainder of both numbers, and then you determine if they’re 0, and if they’re not 0 you divide the remainder by the divisor, and you get a new remainder. And you keep going until you have a remainder of 0, where the divisor is the greatest common divisor.

answer

Method 1: the greatest common divisor

/** * @param {number[]} deck * @return {Boolean} */ var hasGroupsSizeX = function(deck) { %b const GCD = (a, b) => (b === 0? Let map = new map () for (let n of deck) {map.set(n, map.get(n)? map.get(n) + 1 : 1)} // Let arr = [...map.values()] let TMP = arr[0] return arr. Every (I => (TMP = GCD (TMP, I)) > 1)} 68 ms, beat 94.59% of users in all JavaScript commits // Memory consumption: 43.8 MB, beat 6.08% of users in all JavaScript commitsCopy the code

Complexity analysis

  • Time complexity: O(n)
  • Space complexity: O(n)

reference

  • The CARDS are grouped