1250. Check If It Is a Good Array

leetcode hard

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

Task

Дан массив nums из целых положительных чисел. Ваша задача - выбрать некоторое подмножество nums, умножить каждый элемент на целое число и сложить все эти числа.Массив считается хорошим, если из него можно получить сумму, равную 1, при любом возможном подмножестве и множителе. Верните True, если массив хороший, иначе верните False.

Пример:

Input: nums = [12,5,7,23]

Output: true

C# solution

matched/original

public class Solution {
    public bool IsGoodArray(int[] nums) {
        int gcd = nums[0];
        foreach (int num in nums) {
            gcd = Gcd(gcd, num);
            if (gcd == 1) return true;
        }
        return gcd == 1;
    }
    private int Gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = 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 IsGoodArray(vector<int>& nums) {
        int gcd = nums[0];
        foreach (int num in nums) {
            gcd = Gcd(gcd, num);
            if (gcd == 1) return true;
        }
        return gcd == 1;
    }
    private int Gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

Java solution

matched/original

import java.util.Arrays;

public class Solution {
    public boolean isGoodArray(int[] nums) {
        int gcd = nums[0];
        for (int num : nums) {
            gcd = gcd(gcd, num);
            if (gcd == 1) return true;
        }
        return gcd == 1;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

JavaScript solution

matched/original

var isGoodArray = function(nums) {
    let gcd = nums[0];
    for (let num of nums) {
        gcd = gcdFunc(gcd, num);
        if (gcd === 1) return true;
    }
    return gcd === 1;
};

function gcdFunc(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

Python solution

matched/original

import math
from functools import reduce

def isGoodArray(nums):
    return reduce(math.gcd, nums) == 1

Go solution

matched/original

func isGoodArray(nums []int) bool {
    gcd := nums[0]
    for _, num := range nums {
        gcd = gcdFunc(gcd, num)
        if gcd == 1 {
            return true
        }
    }
    return gcd == 1
}

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

Explanation

Algorithm

Если наибольший общий делитель (НОД) всех чисел в массиве равен 1, то массив считается хорошим.

Если НОД всех чисел больше 1, то массив не считается хорошим

Получить сумму, равную 1, умножая и складывая элементы.

😎