GCD of an Array
Easy About 8 min Free, no account needed
The greatest common divisor of many numbers - Euclid, not trial division.
The brief
Return the greatest common divisor of all values in nums (positive
integers).
The obvious approach tries candidate divisors downward from the minimum; when the
answer is 1 and the values are around two billion, that is two billion trial
divisions. The hidden test is exactly that case, so the trial-division scan is
too slow. You will need a method whose cost does not grow with the size of the
values.
Starter code
using System;
public class Solution
{
// TODO: return the GCD of all values.
public int GcdOfArray(int[] nums)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Math and number theory
- Replace enumeration with a formula: GCD, modular arithmetic, digit math and closed-form counting.
Related katas
- Add Binary Strings Easy Free Add two binary numbers far too long for any built-in integer.
- Base64 Decoded Length Easy Free The decoded size is pure arithmetic - no need to decode.
- Count Missing Sample Runs Easy Free Count every contiguous interval with no recorded sample, even when the timeline is too large to expand.
- Excel Column Number Easy Free Spreadsheet columns are base-26 with no zero digit.