C++

Forum

 
Passing Cars

frek (576)
A non-empty array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.

Array A contains only 0s and/or 1s:

0 represents a car traveling east,
1 represents a car traveling west.
The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west.

For example, consider array A such that:

A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).

Write a function:

int solution(vector<int> &A);

that, given a non-empty array A of N integers, returns the number of pairs of passing cars.

The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000.

For example, given:

A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
the function should return 5, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
each element of array A is an integer that can have one of the following values: 0, 1.

Wrote this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
#include <iostream>
#include <vector>
#include <numeric>

int solution(std::vector<int>& A) {
	unsigned int allOns{ std::accumulate(A.begin(), A.end(), 0u) };

	if (allOns == 0 || allOns == A.size())
		return 0;

	unsigned int res{ 0 };

	for (const auto& a : A) 
		if (a == 1) --allOns;
		else {
			res += allOns;
			if (res >= 1'000'000'000)
				return -1;
		}
	return res;
}

int main() {
	std::vector A {1, 1, 1, 0, 0, 1};
	std::cout << solution(A) << '\n';

	return 0;
}


Fine?
Last edited on
DizzyDon (121)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
#include <iostream>
#include <vector>

int solution(std::vector<int>& A) {
    int n = A[0], s = 1, r = 0;
    for (size_t i = 1; i < A.size(); ++i)
        if (A[i] == n)
            ++s;
        else
            r += s;
    return r;
}

int main() {
	std::vector A {1, 1, 1, 0, 0, 1};
	std::cout << solution(A) << '\n';
}

lastchance (6980)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
#include <iostream>
#include <vector>
using namespace std;

int solution( const vector<int> &A )
{
   int eastward = 0, passes = 0;
   for ( int a : A )
   {
      if ( a ) passes += eastward;
      else     eastward++;
      if ( passes >= 1000000000 ) return -1;
   }
   return passes;
}
      
      
int main()
{
   cout << solution( { 0, 1, 0, 1, 1    } ) << '\n';
   cout << solution( { 1, 1, 1, 0, 0, 1 } ) << '\n';
   
   vector<int> A( 100000, 0 );   for ( int i = 50000; i < 100000; i++ ) A[i] = 1;
   cout << solution( A ) << '\n';
}


5
2
-1
Last edited on
frek (576)
We should've used > 1000'000'000 instead. :)
thanks.
Topic archived. No new replies allowed.