4013. Count Subarrays With Even Odd Ratio II

Description

You are given an integer array nums and two integers a and b.

For a subarray, let:

x be the number of even elements.
y be the number of odd elements.

The ratio of even to odd elements in a subarray is defined as x / y, where ratios are compared by their exact rational values.

A subarray is considered valid if:

y > 0, and
x / y <= a / b.

Return the number of valid subarrays in nums.

Example 1:

Input: nums = [1,2,1,2], a = 3, b = 2

Output: 7

Explanation:

The following are the valid subarrays:

Subarray	Values	Even Count	Odd Count	Ratio
`nums[0..0]`	`[1]`	0	1	`0 / 1`
`nums[0..1]`	`[1, 2]`	1	1	`1 / 1`
`nums[0..2]`	`[1, 2, 1]`	1	2	`1 / 2`
`nums[0..3]`	`[1, 2, 1, 2]`	2	2	`2 / 2`
`nums[1..2]`	`[2, 1]`	1	1	`1 / 1`
`nums[2..2]`	`[1]`	0	1	`0 / 1`
`nums[2..3]`	`[1, 2]`	1	1	`1 / 1`

Thus, the number of valid subarrays is 7.

Example 2:

Input: nums = [2,2,1], a = 2, b = 1

Output: 3

Explanation:

The following are the valid subarrays:

Subarray	Values	Even Count	Odd Count	Ratio
`nums[0..2]`	`[2, 2, 1]`	2	1	`2 / 1`
`nums[1..2]`	`[2, 1]`	1	1	`1 / 1`
`nums[2..2]`	`[1]`	0	1	`0 / 1`

Thus, the number of valid subarrays is 3.

Example 3:

Input: nums = [2,2,2], a = 1, b = 1

Output: 0

Explanation:

Every subarray contains 0 odd numbers, so no subarray is valid.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= a, b <= 10⁹

Solutions

Solution 1: Prefix Sum + Binary Indexed Tree

Thinking

The quadratic enumeration of the previous problem does not survive $n=10^5$. The condition $y>0$ and $\frac{x}{y}\le\frac{a}{b}$ rewrites as $ay-bx\ge 0$ when $b>0$; an all-even subarray makes the same expression negative, so both constraints merge.

Mapping odds to $+a$ and evens to $-b$, we count nonempty subarrays whose sum is at least $0$, i.e. prefix pairs with $s[L]\le s[R]$.

Scanning $R$, a Fenwick tree on the compressed prefix values stores how many earlier $s[L]$ have appeared, we query those $\le s[R]$, then insert the current value.

For a subarray, let $x$ be the number of even elements and $y$ be the number of odd elements. The problem requires $y > 0$ and $\frac{x}{y} \le \frac{a}{b}$. Since $b > 0$ and $y > 0$, the inequality is equivalent to $a \cdot y - b \cdot x \ge 0$.

When $y = 0$, since the subarray is non-empty, we must have $x > 0$. In this case, $a \cdot y - b \cdot x = -b \cdot x < 0$, so the inequality does not hold. Therefore, the two conditions in the problem can be merged into a single one: $a \cdot y - b \cdot x \ge 0$.

We treat the odd numbers in $\textit{nums}$ as $a$ and the even numbers as $-b$, resulting in an array $\textit{arr}$. The original problem is then equivalent to counting the number of non-empty contiguous subarrays of $\textit{arr}$ whose element sum is at least $0$.

Let $s$ be the prefix sum array of $\textit{arr}$. The element sum of the subarray $[L, R - 1]$ equals $s[R] - s[L]$, so the problem is further transformed into: how many index pairs $(L, R)$ satisfy $0 \le L < R \le n$ and $s[R] - s[L] \ge 0$, i.e., $s[L] \le s[R]$?

We enumerate $R$ and need to quickly count the number of indices $L$ to the left of $R$ that satisfy $s[L] \le s[R]$. This can be maintained with a Binary Indexed Tree: we first discretize all values in $s$ (sort and deduplicate), then traverse $s$ from left to right. For each value $v = s[R]$, we query the number of inserted elements not greater than $v$ from the Binary Indexed Tree and add it to the answer, then insert $v$ into the tree.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$, where $n$ is the length of the array $\textit{nums}$.

class BinaryIndexedTree {
    private final int n;
    private final int[] c;

    public BinaryIndexedTree(int n) {
        this.n = n;
        this.c = new int[n + 1];
    }

    public void update(int x, int delta) {
        while (x <= n) {
            c[x] += delta;
            x += x & -x;
        }
    }

    public int query(int x) {
        int s = 0;
        while (x > 0) {
            s += c[x];
            x -= x & -x;
        }
        return s;
    }
}

class Solution {
    public long countRatioSubarrays(int[] nums, int a, int b) {
        int n = nums.length;

        long[] s = new long[n + 1];
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + (nums[i] % 2 == 1 ? a : -b);
        }

        long[] st = s.clone();
        Arrays.sort(st);

        int m = 0;
        for (long x : st) {
            if (m == 0 || st[m - 1] != x) {
                st[m++] = x;
            }
        }

        BinaryIndexedTree bit = new BinaryIndexedTree(m + 1);

        long ans = 0;

        for (long v : s) {
            int x = Arrays.binarySearch(st, 0, m, v) + 1;
            ans += bit.query(x);
            bit.update(x, 1);
        }

        return ans;
    }
}

class BinaryIndexedTree {
    int n;
    vector<int> c;

public:
    BinaryIndexedTree(int n)
        : n(n)
        , c(n + 1) {}

    void update(int x, int delta) {
        while (x <= n) {
            c[x] += delta;
            x += x & -x;
        }
    }

    int query(int x) {
        int s = 0;
        while (x > 0) {
            s += c[x];
            x -= x & -x;
        }
        return s;
    }
};

class Solution {
public:
    long long countRatioSubarrays(vector<int>& nums, int a, int b) {
        int n = nums.size();

        vector<long long> s(n + 1);
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + (nums[i] % 2 ? a : -b);
        }

        vector<long long> st = s;
        sort(st.begin(), st.end());
        st.erase(unique(st.begin(), st.end()), st.end());

        BinaryIndexedTree bit(st.size() + 1);

        long long ans = 0;

        for (long long v : s) {
            int x = lower_bound(st.begin(), st.end(), v) - st.begin() + 1;
            ans += bit.query(x);
            bit.update(x, 1);
        }

        return ans;
    }
};

class BinaryIndexedTree:
    __slots__ = "n", "c"

    def __init__(self, n: int):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, delta: int) -> None:
        while x <= self.n:
            self.c[x] += delta
            x += x & -x

    def query(self, x: int) -> int:
        s = 0
        while x:
            s += self.c[x]
            x -= x & -x
        return s


class Solution:
    def countRatioSubarrays(self, nums: list[int], a: int, b: int) -> int:
        n = len(nums)
        s = [0] * (n + 1)
        for i, x in enumerate(nums):
            s[i + 1] = s[i] + (a if x % 2 else -b)

        st = sorted(set(s))
        bit = BinaryIndexedTree(len(st) + 1)
        ans = 0
        for v in s:
            x = bisect_left(st, v) + 1
            ans += bit.query(x)
            bit.update(x, 1)
        return ans

type BinaryIndexedTree struct {
	n int
	c []int
}

func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
	return &BinaryIndexedTree{
		n: n,
		c: make([]int, n+1),
	}
}

func (bit *BinaryIndexedTree) update(x int, delta int) {
	for x <= bit.n {
		bit.c[x] += delta
		x += x & -x
	}
}

func (bit *BinaryIndexedTree) query(x int) int {
	sum := 0
	for x > 0 {
		sum += bit.c[x]
		x -= x & -x
	}
	return sum
}

func countRatioSubarrays(nums []int, a int, b int) int64 {
	n := len(nums)

	s := make([]int64, n+1)

	for i, x := range nums {
		if x%2 == 1 {
			s[i+1] = s[i] + int64(a)
		} else {
			s[i+1] = s[i] - int64(b)
		}
	}

	st := append([]int64{}, s...)
	sort.Slice(st, func(i, j int) bool {
		return st[i] < st[j]
	})

	uniq := make([]int64, 0, len(st))
	for _, x := range st {
		if len(uniq) == 0 || uniq[len(uniq)-1] != x {
			uniq = append(uniq, x)
		}
	}

	bit := NewBinaryIndexedTree(len(uniq) + 1)

	var ans int64

	for _, v := range s {
		x := sort.Search(len(uniq), func(i int) bool {
			return uniq[i] >= v
		}) + 1

		ans += int64(bit.query(x))
		bit.update(x, 1)
	}

	return ans
}

class BinaryIndexedTree {
    private n: number;
    private c: number[];

    constructor(n: number) {
        this.n = n;
        this.c = new Array(n + 1).fill(0);
    }

    update(x: number, delta: number): void {
        while (x <= this.n) {
            this.c[x] += delta;
            x += x & -x;
        }
    }

    query(x: number): number {
        let sum = 0;
        while (x > 0) {
            sum += this.c[x];
            x -= x & -x;
        }
        return sum;
    }
}

function countRatioSubarrays(nums: number[], a: number, b: number): number {
    const n = nums.length;

    const s = new Array<number>(n + 1).fill(0);

    for (let i = 0; i < n; i++) {
        s[i + 1] = s[i] + (nums[i] % 2 === 1 ? a : -b);
    }

    const st = [...s].sort((x, y) => x - y);

    const uniq: number[] = [];
    for (const x of st) {
        if (uniq.length === 0 || uniq[uniq.length - 1] !== x) {
            uniq.push(x);
        }
    }

    const bit = new BinaryIndexedTree(uniq.length + 1);

    let ans = 0;

    for (const v of s) {
        const x = _.sortedIndex(uniq, v) + 1;

        ans += bit.query(x);
        bit.update(x, 1);
    }

    return ans;
}

struct BinaryIndexedTree {
    n: usize,
    c: Vec<i32>,
}

impl BinaryIndexedTree {
    fn new(n: usize) -> Self {
        Self {
            n,
            c: vec![0; n + 1],
        }
    }

    fn update(&mut self, mut x: usize, delta: i32) {
        while x <= self.n {
            self.c[x] += delta;
            x += x & (!x + 1);
        }
    }

    fn query(&self, mut x: usize) -> i32 {
        let mut s = 0;
        while x > 0 {
            s += self.c[x];
            x &= x - 1;
        }
        s
    }
}

impl Solution {
    pub fn count_ratio_subarrays(nums: Vec<i32>, a: i32, b: i32) -> i64 {
        let n = nums.len();

        let mut s = vec![0i64; n + 1];

        for i in 0..n {
            s[i + 1] = s[i]
                + if nums[i] % 2 == 1 {
                    a as i64
                } else {
                    -(b as i64)
                };
        }

        let mut st = s.clone();
        st.sort_unstable();
        st.dedup();

        let mut bit = BinaryIndexedTree::new(st.len() + 1);

        let mut ans = 0i64;

        for v in s {
            let x = match st.binary_search(&v) {
                Ok(i) => i,
                Err(i) => i,
            } + 1;

            ans += bit.query(x) as i64;
            bit.update(x, 1);
        }

        ans
    }
}

4013 - Count Subarrays With Even Odd Ratio II

4013. Count Subarrays With Even Odd Ratio II

Description

Solutions

Solution 1: Prefix Sum + Binary Indexed Tree

All Problems

All Solutions

Welcome to Subscribe On Youtube

4013. Count Subarrays With Even Odd Ratio II

Description

Solutions

Solution 1: Prefix Sum + Binary Indexed Tree

All Problems

All Solutions