# L5-PassingCars
###### tags: `Codility_lessons`
## Question
https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/
## Key
1. 本來用一個loop遍尋對為0的車子再用一個loop往後找有幾個1的車子，但這樣會time exceed，且題目沒有要求個別0的車子對應到幾個1的車子，只要求總和就好
2. 所以改用Prefix sum。一個loop以找到的0的車子為基數，對1的車子做累加，且剛好是從小到大遍尋，0的車子一定會配到比自己位置大的1的車子
3. 注意極值，還有讓測資更多元，算法才能更實用
## Reference
## Solution

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int A_size = A.size();
    long count = 0;
    int add_base = 0;
    for(int i = 0; i<A_size; i++)
    {
        if(A[i] == 0)
        {
            add_base++;
        }
        else 
        {
            count += add_base;
        }
    }
    if(count > 1000000000)
        return -1;
    return count;
}