leetcode weekly 119 - Subarray Sums Divisible by K

974. Subarray Sums Divisible by K

Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K. 

Example 1:

Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Note:

1. 1 <= A.length <= 30000
2. -10000 <= A[i] <= 10000
3. 2 <= K <= 10000

---

Solution by neal_wu (Rank #3) in contest
Idea:

• See: https://leetcode.com/articles/subarray-sums-divisible-by-k/
• Calculate prefix sum of A, say P[i+1] = A[0] + ... + A[i], so subarray sum can be represented as P[j] - P[i] (j > i)
• Say C[i] = Count P[i] % K, i = 0..K-1
• Calculate combination sum for C[i] with i = 0..K-1

class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        int n = A.size();
        vector<int> prefix_sum(n + 1, 0);

        for (int i = 0; i < n; i++)
            prefix_sum[i + 1] = ((prefix_sum[i] + A[i]) % K + K) % K;

C++

Note! Because prefix_sum can be negative, so here need ((..)% K + K) % K;

• If prefix sum >= 0, the result is unchanged
• If prefix sum < 0, the result is complement value, e.g. P = -2, K = 3, ((P % K) + K) % K = 1

        vector<int> freq(K, 0);
        long long total = 0;

        for (int i = 0; i <= n; i++) {
            total += freq[prefix_sum[i]];
            freq[prefix_sum[i]]++;
        }

        return total;
    }
};

C++

---

My second try after reading the answer. (I count positive and negative prefix sum separately)

  int subarraysDivByK(vector<int>& A, int K) {
    const int n = A.size();
    vector<int> prefsum(n + 1, 0);
    for (int i = 0; i < n; ++i)
      prefsum[i + 1] = prefsum[i] + A[i];
    
    vector<int> count(K, 0); // 0 ~ K-1
    vector<int> negCount(K+1, 0); // -K+1 ~ 0
    for (int p : prefsum) {
      int r = p % K;
      if (r < 0)
        ++negCount[abs(r)];
      else
        ++count[r];
    }
      
    int ans = 0;
    for (int i = 0; i < K; ++i) {
      int combine = count[i] + negCount[K - i];
      ans += combine * (combine - 1) / 2;
    }

    return ans;
  }

C++

leetcode weekly 118 - Equal Rational Numbers

972. Equal Rational Numbers

Given two strings S and T, each of which represents a non-negative rational number, return True if and only if they represent the same number. The strings may use parentheses to denote the repeating part of the rational number.

In general a rational number can be represented using up to three parts: an integer part, a non-repeating part, and a repeating part. The number will be represented in one of the following three ways:

• <IntegerPart> (e.g. 0, 12, 123)
• <IntegerPart><.><NonRepeatingPart>  (e.g. 0.5, 1., 2.12, 2.0001)
• <IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)> (e.g. 0.1(6), 0.9(9), 0.00(1212))

The repeating portion of a decimal expansion is conventionally denoted within a pair of round brackets.  For example:

1 / 6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66)

Both 0.1(6) or 0.1666(6) or 0.166(66) are correct representations of 1 / 6.

Example 1:

Input: S = "0.(52)", T = "0.5(25)"
Output: true
Explanation:
Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

Example 2:

Input: S = "0.1666(6)", T = "0.166(66)"
Output: true

Example 3:

Input: S = "0.9(9)", T = "1."
Output: true
Explanation: 
"0.9(9)" represents 0.999999999... repeated forever, which equals 1.  [See this link for an explanation.]
"1." represents the number 1, which is formed correctly: (IntegerPart) = "1" and (NonRepeatingPart) = "".

Note:

1. Each part consists only of digits.
2. The <IntegerPart> will not begin with 2 or more zeros.  (There is no other restriction on the digits of each part.)
3. 1 <= <IntegerPart>.length <= 4
4. 0 <= <NonRepeatingPart>.length <= 4
5. 1 <= <RepeatingPart>.length <= 4

---

Solution by neal_wu (Rank #1) in contest (Very elegant solution!)
Idea:

• Represent the number in "irreducible fraction" form  
• a and b can exceed 32-bit integer, so use 64-bit integer to store a and b
• Fraction can naturally represent repeat part

struct fraction {
    int64_t numer, denom;

    void reduce() {
        int64_t g = __gcd(numer, denom);
        numer /= g;
        denom /= g;
    }

    bool operator==(const fraction &other) const {
        return numer == other.numer && denom == other.denom;
    }
};

int64_t power10(int n) {
    return n == 0 ? 1 : 10 * power10(n - 1);
}

fraction to_fraction(string S) {
    size_t period = S.find('.');

    if (period == string::npos)
        return {stoll(S), 1};

    int64_t integer = stoll(S.substr(0, period));
    S = S.substr(period + 1);

    if (S.empty())
        return {integer, 1};

    size_t paren = S.find('(');

    if (paren == string::npos) {
        int n = S.size();
        int64_t p = power10(n);
        return {integer * p + stoll(S), p};
    }

    int64_t p = power10(paren);
    int64_t nonrepeating = paren == 0 ? 0 : stoll(S.substr(0, paren));

    string remaining = S.substr(paren + 1, S.size() - 1 - (paren + 1));
    int64_t rp = power10(remaining.size()) - 1;

C++

Why rp = power10(remaining.size()) - 1? Because the repeating part is calculated by geometric series,
e.g. 0.(123)

    int64_t repeating = stoll(remaining);
    return {integer * p * rp + nonrepeating * rp + repeating, p * rp};
}

class Solution {
public:
    bool isRationalEqual(string S, string T) {
        fraction A = to_fraction(S);
        fraction B = to_fraction(T);
        A.reduce();
        B.reduce();
        return A == B;
    }
};

C++

llvm weekly 260 - thread group; parallel stl impl.

1. [RFC] Thread group semantics 
2. Intel's Parallel STL implementation