914. X of a Kind in a Deck of Cards

leetcode easy

#array#csharp#easy#hash-table#leetcode#math

Task

Вам дан целочисленный массив deck, где deck[i] - число, написанное на i-й карте. Разделите карты на одну или несколько групп так, чтобы: в каждой группе было ровно x карт, где x > 1, и на всех картах в одной группе было написано одно и то же целое число. Верните true, если такое разделение возможно, или false в противном случае.

Пример:

Input: deck = [1,2,3,4,4,3,2,1]

Output: true

C# solution

matched/original

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
    public bool HasGroupsSizeX(int[] deck) {
        var count = deck.GroupBy(x => x).ToDictionary(g => g.Key, g => g.Count());
        var freqValues = count.Values.ToList();
        var g = freqValues.Aggregate(Gcd);
        return g > 1;
    }
    private int Gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool HasGroupsSizeX(vector<int>& deck) {
        var count = deck.GroupBy(x => x).ToDictionary(g => g.Key, g => g.size()());
        var freqValues = count.Values.ToList();
        var g = freqValues.Aggregate(Gcd);
        return g > 1;
    }
    private int Gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}

Java solution

matched/original

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : deck) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        
        int g = count.values().stream().reduce(this::gcd).orElse(0);
        return g > 1;
    }
    
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}

JavaScript solution

matched/original

var hasGroupsSizeX = function(deck) {
    const count = deck.reduce((acc, num) => {
        acc[num] = (acc[num] || 0) + 1;
        return acc;
    }, {});
    
    const freqValues = Object.values(count);
    const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
    const g = freqValues.reduce((acc, val) => gcd(acc, val));
    
    return g > 1;
};

Python solution

matched/original

from collections import Counter
from math import gcd
from functools import reduce

def hasGroupsSizeX(deck):
    count = Counter(deck)
    freq_values = list(count.values())
    g = reduce(gcd, freq_values)
    return g > 1

Go solution

matched/original

package main

func hasGroupsSizeX(deck []int) bool {
    count := map[int]int{}
    for _, num := range deck {
        count[num]++
    }

    gcd := func(a, b int) int {
        for b != 0 {
            a, b = b, a%b
        }
        return a
    }

    g := 0
    for _, freq := range count {
        g = gcd(g, freq)
    }

    return g > 1
}

Explanation

Algorithm

1⃣Создать словарь для подсчета частоты каждого числа в массиве deck.

2⃣Найти наибольший общий делитель (НОД) всех частот.

3⃣Проверить, больше ли НОД 1, чтобы определить, можно ли разделить карты на группы.

😎