Codility passing car
|
12:18 AM |
No comments |
Codility passing car
A non-empty zero-indexed 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:
class Solution { public int solution(int[] A); } that, given a non-empty zero-indexed array A of N integers, returns the number of passing cars.
The function should return ?1 if the number 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.
Assume that:
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. Complexity:
expected worst-case time complexity is O(N); expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified.
I don't understand why there are five passing cars, instead of 6. Why doesn't (2,1) count as a passing car? Can someone provide some explanation on how to approach this problem?
Answer by Kromster for Codility passing car
You need to count number of cars passings. Cars are positioned on the road as input says and start driving into either one of directions. When car drives, we can easily see that it will drive by cars moving in the opposite direction, but only if they were in front of it. Essentially that can be formulated as:
Imagine array 0..N
Take element X (iterate from 0 to Nth element)
If value of element X is 0 then count how many 1 elements it has on the right
If value of element X is 1 then count how many 0 elements it has on left
Repeat for next X
Sum up and divide by 2 (cos it takes 2 cars to pass each other), that's the answer.
In case with 0 1 0 1 1 we have 3+1+2+2+2 = 10. Divide by 2 = 5 passings.
We don't count pair 2-1 because 2nd car is driving to the East and never passes the 1st car that is driving away from it to the West.
Answer by user3662248 for Codility passing car
Time Complexity - O(n) Space Complexity - O(1) The logic I came up with goes like this.
- Have 2 variables. Count and IncrementVal. Initialize both to zero.
- Traverse through the array. Every time you find a 0, increment the IncrementVal.
- Every time you find a 1, modify count by adding the incrementVal to count.
- After the array traversal is completed, return back the count.
Note:: Example code provided below assumes static array and a predefined array size. You can make it dynamic using vectors.
#include using namespace std; int getPass(int* A, int N) { unsigned long count = 0; int incrementVal = 0; for(int i = 0; i < N; i++) { if(A[i]==0) { incrementVal++; } else if (A[i]==1) { count = count + incrementVal; } if(count > 1000000000) return -1; } return count; } int main() { int A[]={0,1,0,1,1}; int size = 5; int numPasses = getPass(A,size); cout << "Number of Passes: " << numPasses << endl; } Answer by swingkid for Codility passing car
def prefix_sums(A): n = len(A) p = [0] * (n + 1) for k in xrange(1, n + 1): p[k] = p[k - 1] + A[k - 1] return p
time complexity I believe is O(N^2)
def solution(A): lenA = len(A) x = 0 numPassingCars = 0 for i in A: x += 1 for j in A[x:]: if i == 0 and j == 1: numPassingCars += 1 if numPassingCars > 1000000000: return -1 return numPassingCars
I belive time complexity is O(N^2)
def solution2(A):
lenA = len(A) numPassingCars = 0 counter = 0 for x in A: counter += 1 if x == 0: numPassingCars += sum(A[counter:]) if numPassingCars > 1000000000: return -1 return numPassingCars I belive time complexity is O(N)
def solution3(A):
lenA = len(A) numPassingCars = 0 counter = 0 ps = prefix_sums(A) for x in A: if x == 0: numPassingCars += (ps[lenA] - ps[counter]) if numPassingCars > 1000000000: return -1 counter += 1 return numPassingCars B = [0, 1, 0, 1, 1]
print solution(B) print solution2(B) print solution3(B)
Output:
5 5 5 Answer by tas for Codility passing car
We need only to traverse the Zeros, in order to find the number of total crossings.
No need to run extra code for Ones, because the number of crossings for every Zero we check, is equal to the number of crossings we get, when we check all Ones for that particular Zero.
public class passingCars { public static void main(String[] args) { int k; int cnt = 0; // Test array int[] A = { 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1 }; for (int i = 0; i < A.length; i++) { if (A[i] == 0) { k = i + 1; while (k < A.length) { if (A[k] == 1) { cnt++; } k++; } } } System.out.println(cnt); } } result: 17
Answer by Tanel for Codility passing car
Here is my code that got 100% in C#
class Solution { public int solution(int[] A) { int count = 0; int multiply = 0; foreach (int car in A) { if (car == 0) { multiply = multiply + 1; } if (multiply > 0) { if (car == 1) { count = count + multiply; if (count > 1000000000) { return -1; } } } } return count; } } Answer by Koin Arab for Codility passing car
This is simple example in Java. I think it should be passed on 100%
public int solution(int[] A) { int countOfZeros = 0, count = 0; for (int i = 0; i < A.length; i++){ if (A[i] == 0) countOfZeros++; if (A[i] == 1) count += countOfZeros; if (count > 1000000000) return -1; } return count; } Answer by bagusflyer for Codility passing car
Objective-c function:
-(int)carPairCount:(NSMutableArray *)A { if ( A.count > 0 ) { int N = (int)A.count; int P = 0; int Q = 1; int count = 0; while ( P < QAnswer by Balaji Reddy for Codility passing car
Passing cars solution in C
int solution(int A[], int N) { // write your code in C90 int i=N-1,j=0,k=0; do { if (A[i]==0) { j+=k; if (j>1000000000)return -1; } else k += 1; }while(--i>=0); return j; } Answer by Shpend S. Sokoli for Codility passing car
Passing cars solution in PHP (100% on Codility)
function solution($A) { $count = 0; $helper = 0; for($i=0;$i 1000000000) return -1; } return $count; } Answer by Beri for Codility passing car
100%/100% Performance in Java.
public int solution(int[] A) { if (A.length == 1) { return 0; } long westCars = 0; for (int i : A) { westCars += i; } long counter = 0; for (int i : A) { if (i == 0) { counter += westCars; } else { westCars--; } } if (counter > 1000000000) { return -1; } return (int) counter; } Answer by Siegfried for Codility passing car
Here is my solution in C, it scores 100% and is quite simple to understand. The trick is to go backwards through the array
int solution(int A[], int N) { int goingWest = 0; int passes = 0; for(int i = N-1; i >= 0; i--) { if(A[i] == 1) { goingWest++; } else { passes += goingWest; if(passes > 1000000000) return -1; } } return passes; }
Answer by Fawad Masud for Codility passing car
Objectve-C solution 100%
int solution(NSMutableArray *A) { // write your code in Objective-C 2.0 int n=0; int long long t = 0; for(int i=0;i1000000000) { return -1; } else { return t; } } Answer by Adnan Aftab for Codility passing car
In Objective-c With 100% https://codility.com/demo/results/demoKEEN2X-N8V/
int passingCars(NSMutableArray* a) { if (a.count <= 1) { return 0; } int passingCars = 0; int goingEast = 0; for (int i = 0; i < a.count; i ++) { if ([a[i] intValue] == 0) { goingEast++; } else { passingCars += goingEast; if (passingCars > 1000000000) { return -1; } } } return passingCars; } Answer by Maya for Codility passing car
Solution in Java, 100% in codility:
public int solution(int[] A) { int countZro = 0; int countCars = 0; for(int i=0; i 0 && A[i]==1 ) { countCars += countZro; } if(countCars>1000000000) { return -1; } } return countCars; } Answer by user1998535 for Codility passing car
C# : anyone shorter ? ;-)
public int solution(int[] cars, int N) { var sum = 0; for (var i = 0; i < N; i++) { if (cars[i]==1) continue; sum += cars.Skip(i).Aggregate((a, b) => a + b); if (sum > 1000000000) return -1; } return sum; } Answer by Min2 for Codility passing car
Java: I did it in simple way 100% correctness and performance
public int solution(int[] A) { // write your code in Java SE 8 int output = 0; int noOfZero = 0; for (int i = 0; i < A.length; i++) { if (A[i] == 0) { noOfZero += 1; continue; } if (A[i] == 1 && noOfZero > 0) { output += noOfZero * A[i]; } } if(output > 1000000000 || output < 0){ return -1; } return output; } Answer by V Malhi for Codility passing car
Code in VB.NET with 100 accuracy and Performance
Private Function solution(A As Integer()) As Integer ' write your code in VB.NET 4.0 Dim i, size As Integer Dim ECars, WCars, Sum As Long size = A.Length ECars = 0 WCars = 0 For i = 0 to size - 1 If A(i) = 0 Then ECars += 1 End If If ECars > 0 And A(i) = 1 Then Sum + = ECars End If Next If Sum > 1000000000 Then Sum = -1 End If Return CInt(Sum) End Function Answer by CoderUser for Codility passing car
C# solutiion:
public int solution(int[] A) { // write your code in C# 6.0 with .NET 4.5 (Mono) int carsEast = 0; int carPairs = 0; for (int i = 0; i < A.Length; i++) { carsEast = A[i] == 0 ? carsEast+=1 : carsEast; carPairs = A[i] == 1 && carsEast > 0 ? carPairs + carsEast : carPairs; if (carPairs > 1000000000) { return -1; } } return carPairs; }Answer by Artem for Codility passing car
My Solution : 100\100 on C#
public int solution(int[] A) { // write your code in C# 6.0 with .NET 4.5 (Mono) int west = 0; // 1 int east = 0; // 0 int pairsCounter = 0; if (A.Length < 0 || A.Length > 100000) return 0; if (A.Length == 2 && A[0] == 0 && A[1] == 1) return 1; // finds all west moving cars for (int i = 0; i < A.Length; i++) { if (A[i] == 1) west++; } east = A.Length - west; if (east == 0 || west == 0) return 0; //if (east >= west) // a possible error in test case on codility. It let it be the situation when P >= Q situation, while P < Q < N // return 0; for (int i = 0; (i < A.Length && west > 0); i++) { if (A[i] == 0 && west > 0) { // calculates the combinations pairsCounter = pairsCounter + west; } else { west--; } if (pairsCounter > 1000000000) return -1; } return pairsCounter; } Answer by Rees for Codility passing car
if it helps conceptually, think of the positions of the cars as all parked, engines off and facing either east or west in the order of the array. then they all start their engines and then start driving... thus, car #2 and car #1 never pass each other.
0 comments:
Post a Comment