sm.pavlenko
BAN USER
Comments (4)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote
The most efficient way is only when we are swapping only 0<->1 (not 0<->0 and not 1<->1)
So we have to count "1" on the left side of each "0".
public int countMoves(String stext) {
int oneCount = 0;
int result = 0;
char[] ch = stext.toCharArray();
for (int i = 0; i < ch.length; ++i) {
if (ch[i] == '1') {
oneCount++;
} else {
result += oneCount;
}
}
return result;
}
Complexity = O(n)
- sm.pavlenko February 01, 2013Comment hidden because of low score. Click to expand.
0
of 0 vote
The answer is correct. And it's (X+Y)!/X!*Y!
For more info read about Pascal's triangle.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Step 4 is wrong.
Suppose we have words "a" and "b".
The arrays would be a[][]=[1][0] and b[][]=[0][1].
The result would be sum=0 which means that "a" and "b" are completely equals.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Solution is straightforward:
- sm.pavlenko February 01, 20131) Iterate through A (i=0..a)
2) Iterate through B (j=0..b)
3) Binary search A[i]-B[j] in C
Complexity: O(A*B*logC)
Space: O(1)
I don't think sorting approaches will give more efficiency because any sorting algorithm has complexity at least n*logn