Counting Trading Sequences
- Source
- Confirmed — December 2025 OA · dev.to report
- Statement
-
Given a sequence of n stock prices (provided as decimal strings),
count all profitable trading pairs
(i, j)such thati < jandprice[j] > price[i]. Return the count modulo 109 + 7. - Constraints
- 1 ≤ n ≤ 105 · prices given as decimal strings · time limit ~2 s
- Example
-
Input: ["1.5", "3.0", "2.5", "4.0", "2.0"] Output: 6 Profitable pairs (buy_idx → sell_idx): (0,1) 1.5 → 3.0 ✓ (1,3) 3.0 → 4.0 ✓ (0,2) 1.5 → 2.5 ✓ (2,3) 2.5 → 4.0 ✓ (0,3) 1.5 → 4.0 ✓ (0,4) 1.5 → 2.0 ✓ Count = 6
Pitfall — Floating-Point Precision
The most-reported failure mode: using Python's float() causes
approximately 89 % of test cases to fail when prices have
many decimal places. Use Decimal instead.
# Wrong — float loses precision at high decimal depth prices = [float(p) for p in price_strings] # Correct — Decimal stores the value exactly from decimal import Decimal prices = [Decimal(p) for p in price_strings]
This single issue is why candidates with correct logic score 0–30 %.
Hint — Brute Force vs Optimal
Brute force O(n²): two nested loops — correct but times out for n = 105.
def count_pairs_slow(prices):
MOD, n, count = 10**9+7, len(prices), 0
for i in range(n):
for j in range(i+1, n):
if prices[j] > prices[i]:
count = (count + 1) % MOD
return count
Optimal O(n log n) — Fenwick Tree: for each index j, count
how many elements to its left are strictly less than price[j].
This is the classic "count smaller to the left" query.
- Sort all unique Decimal prices and assign integer ranks 1, 2, …, k.
- Iterate left to right. For price at rank r: query BIT for prefix sum up to r−1.
- Accumulate (mod 10⁹+7). Update BIT at rank r.
Solution — Python Reference
from decimal import Decimal
from typing import List
MOD = 10**9 + 7
def _update(bit: list, i: int, n: int) -> None:
while i <= n:
bit[i] += 1
i += i & (-i)
def _query(bit: list, i: int) -> int:
s = 0
while i > 0:
s += bit[i]
i -= i & (-i)
return s
def count_profitable_pairs(price_strings: List[str]) -> int:
prices = [Decimal(p) for p in price_strings] # Critical: Decimal
sorted_unique = sorted(set(prices))
rank = {v: i + 1 for i, v in enumerate(sorted_unique)}
m = len(sorted_unique)
bit = [0] * (m + 2)
result = 0
for p in prices:
r = rank[p]
result = (result + _query(bit, r - 1)) % MOD
_update(bit, r, m)
return result
assert count_profitable_pairs(["1.5","3.0","2.5","4.0","2.0"]) == 6
assert count_profitable_pairs(["5.0","4.0","3.0","2.0","1.0"]) == 0
assert count_profitable_pairs(["1.0","2.0","3.0","4.0","5.0"]) == 10