jakobkogler / algorithm-datastructures Goto Github PK

a/=b fails if a and b are bigint, i.e, division overloading has not been done bigint/bigint.

CeilFloorDivision.h works incorrectly in cases where $b < 0$ one of them is $a = -5$ and $b = -2$.

The correct answer is $\lceil \frac{a}{b} \rceil = 3$ and $\lfloor \frac{a}{b} \rfloor = 2$. But your code returns $\lceil \frac{a}{b} \rceil = 2$ and $\lfloor \frac{a}{b} \rfloor = 1$.

Another case: $a = 5$ and $b = -2$. Correct answer: $\lceil \frac{a}{b} \rceil = -2$ and $\lfloor \frac{a}{b} \rfloor = -3$.

Making $b$ positive before doing any computation works.

template <typename T>
T floor_div(T a, long long b) {
    if (b < 0) { 
        a = -a;
        b = std::abs(b);
    }
    return (a < 0 ? a - (b - 1) : a) / b;
}

template <typename T>
T ceil_div(T a, long long b) {
    if (b < 0) {
        a = -a;
        b = std::abs(b);
    }
    return (a >= 0 ? a + (b - 1) : a) / b;
}