Sorry, but your solution is still O(N^2)\$O(N^2)\$. Say the number of 1s is its minimum. Consider the minimum number of 1s, i.e. each row i has i+1 ones. You will have to scan N-i\$N-i\$ positions in each row, for a total of N^2/2\$N^2/2\$ actions, i.e. O(N^2)\$O(N^2)\$. visually:
1* 0* 0* 0* 0*
1 1* 0* 0* 0*
1 1 1* 0* 0*
1 1 1 1* 0*
1 1 1 1 1*
Where the *s indicate you looked at that position.
With smart enough code, you could actually infer the 1s, but that's still O(N^2)\$O(N^2)\$ and probably more overhead than it's worth.
A faster solution is to find the border between 0 and 1 by binary search.
int findFirstZero(int *row, int left, int right)
{
if(row[right]) return right;
int lastOne = left;
int firstZero = right;
int pos;
while(firstZero - lastOne > 1) {
pos = (lastOne + firstZero) / 2;
if(pos) {
lastOne = pos;
} else {
firstZero = pos;
}
}
return firstZero;
}
int sumOnes(int **map) {
int sum = 0;
for(int i = 0; i < N; i++) {
sum += findFirstZero(map[i], i, N-i-1);
}
return sum;
}
Now, this is actually O(NlogN)\$O(NlogN)\$, but given the constraints of the problem as I understand them, I'm quite certain that's the best possible; either you or Cormen left something out of the problem or Cormen made a mistake in his big-O analysis. I'd love to see a proof to the contrary, though.
Sorry, but your solution is still O(N^2). Say the number of 1s is its minimum. Consider the minimum number of 1s, i.e. each row i has i+1 ones. You will have to scan N-i positions in each row, for a total of N^2/2 actions, i.e. O(N^2). visually:
1* 0* 0* 0* 0*
1 1* 0* 0* 0*
1 1 1* 0* 0*
1 1 1 1* 0*
1 1 1 1 1*
Where the *s indicate you looked at that position.
With smart enough code, you could actually infer the 1s, but that's still O(N^2) and probably more overhead than it's worth.
A faster solution is to find the border between 0 and 1 by binary search.
int findFirstZero(int *row, int left, int right)
{
if(row[right]) return right;
int lastOne = left;
int firstZero = right;
int pos;
while(firstZero - lastOne > 1) {
pos = (lastOne + firstZero) / 2;
if(pos) {
lastOne = pos;
} else {
firstZero = pos;
}
}
return firstZero;
}
int sumOnes(int **map) {
int sum = 0;
for(int i = 0; i < N; i++) {
sum += findFirstZero(map[i], i, N-i-1);
}
return sum;
}
Now, this is actually O(NlogN), but given the constraints of the problem as I understand them, I'm quite certain that's the best possible; either you or Cormen left something out of the problem or Cormen made a mistake in his big-O analysis. I'd love to see a proof to the contrary, though.
Sorry, but your solution is still \$O(N^2)\$. Say the number of 1s is its minimum. Consider the minimum number of 1s, i.e. each row i has i+1 ones. You will have to scan \$N-i\$ positions in each row, for a total of \$N^2/2\$ actions, i.e. \$O(N^2)\$. visually:
1* 0* 0* 0* 0*
1 1* 0* 0* 0*
1 1 1* 0* 0*
1 1 1 1* 0*
1 1 1 1 1*
Where the *s indicate you looked at that position.
With smart enough code, you could actually infer the 1s, but that's still \$O(N^2)\$ and probably more overhead than it's worth.
A faster solution is to find the border between 0 and 1 by binary search.
int findFirstZero(int *row, int left, int right)
{
if(row[right]) return right;
int lastOne = left;
int firstZero = right;
int pos;
while(firstZero - lastOne > 1) {
pos = (lastOne + firstZero) / 2;
if(pos) {
lastOne = pos;
} else {
firstZero = pos;
}
}
return firstZero;
}
int sumOnes(int **map) {
int sum = 0;
for(int i = 0; i < N; i++) {
sum += findFirstZero(map[i], i, N-i-1);
}
return sum;
}
Now, this is actually \$O(NlogN)\$, but given the constraints of the problem as I understand them, I'm quite certain that's the best possible; either you or Cormen left something out of the problem or Cormen made a mistake in his big-O analysis. I'd love to see a proof to the contrary, though.
Sorry, but your solution your solution is still O(N^2). Say the number of 1s is its minimum. Consider the minimum number of 1s, i.e. each row i has i+1 ones. You will have to scan N-i positions in each row, for a total of N^2/2 actions, i.e. O(N^2). visually:
1* 0* 0* 0* 0*
1 1* 0* 0* 0*
1 1 1* 0* 0*
1 1 1 1* 0*
1 1 1 1 1*
Where the *s indicate you looked at that position.
With smart enough code, you could actually infer the 1s, but that's still O(N^2) and probably more overhead than it's worth.
A faster solution is to find the border between 0 and 1 by binary search.
int findFirstZero(int *row, int left, int right)
{
if(row[right]) return right;
int lastOne = left;
int firstZero = right;
int pos;
while(firstZero - lastOne > 1) {
pos = (lastOne + firstZero) / 2;
if(pos) {
lastOne = pos;
} else {
firstZero = pos;
}
}
return firstZero;
}
int sumOnes(int **map) {
int sum = 0;
for(int i = 0; i < N; i++) {
sum += findFirstZero(map[i], i, N-i-1);
}
return sum;
}
Now, this is actually O(NlogN), but given the constraints of the problem as I understand them, I'm quite certain that's the best possible; either you or Cormen left something out of the problem or Cormen made a mistake in his big-O analysis. I'd love to see a proof to the contrary, though.
Sorry, but your solution is still O(N^2). Say the number of 1s is its minimum. Consider the minimum number of 1s, i.e. each row i has i+1 ones. You will have to scan N-i positions in each row, for a total of N^2/2 actions, i.e. O(N^2). visually:
1* 0* 0* 0* 0*
1 1* 0* 0* 0*
1 1 1* 0* 0*
1 1 1 1* 0*
1 1 1 1 1*
Where the *s indicate you looked at that position.
With smart enough code, you could actually infer the 1s, but that's still O(N^2) and probably more overhead than it's worth.
A faster solution is to find the border between 0 and 1 by binary search.
int findFirstZero(int *row, int left, int right)
{
if(row[right]) return right;
int lastOne = left;
int firstZero = right;
int pos;
while(firstZero - lastOne > 1) {
pos = (lastOne + firstZero) / 2;
if(pos) {
lastOne = pos;
} else {
firstZero = pos;
}
}
return firstZero;
}
int sumOnes(int **map) {
int sum = 0;
for(int i = 0; i < N; i++) {
sum += findFirstZero(map[i], i, N-i-1);
}
return sum;
}
Now, this is actually O(NlogN), but given the constraints of the problem as I understand them, I'm quite certain that's the best possible; either you or Cormen left something out of the problem or Cormen made a mistake in his big-O analysis. I'd love to see a proof to the contrary, though.
Sorry, but your solution is still O(N^2). Say the number of 1s is its minimum. Consider the minimum number of 1s, i.e. each row i has i+1 ones. You will have to scan N-i positions in each row, for a total of N^2/2 actions, i.e. O(N^2). visually:
1* 0* 0* 0* 0*
1 1* 0* 0* 0*
1 1 1* 0* 0*
1 1 1 1* 0*
1 1 1 1 1*
Where the *s indicate you looked at that position.
With smart enough code, you could actually infer the 1s, but that's still O(N^2) and probably more overhead than it's worth.
A faster solution is to find the border between 0 and 1 by binary search.
int findFirstZero(int *row, int left, int right)
{
if(row[right]) return right;
int lastOne = left;
int firstZero = right;
int pos;
while(firstZero - lastOne > 1) {
pos = (lastOne + firstZero) / 2;
if(pos) {
lastOne = pos;
} else {
firstZero = pos;
}
}
return firstZero;
}
int sumOnes(int **map) {
int sum = 0;
for(int i = 0; i < N; i++) {
sum += findFirstZero(map[i], i, N-i-1);
}
return sum;
}
Now, this is actually O(NlogN), but given the constraints of the problem as I understand them, I'm quite certain that's the best possible; either you or Cormen left something out of the problem or Cormen made a mistake in his big-O analysis. I'd love to see a proof to the contrary, though.
Sorry, but your solution is still O(N^2). Say the number of 1s is its minimum. Consider the minimum number of 1s, i.e. each row i has i+1 ones. You will have to scan N-i positions in each row, for a total of N^2/2 actions, i.e. O(N^2). visually:
1* 0* 0* 0* 0*
1 1* 0* 0* 0*
1 1 1* 0* 0*
1 1 1 1* 0*
1 1 1 1 1*
Where the *s indicate you looked at that position.
With smart enough code, you could actually infer the 1s, but that's still O(N^2) and probably more overhead than it's worth.
A faster solution is to find the border between 0 and 1 by binary search.
int findFirstZero(int *row, int left, int right)
{
if(row[right]) return right;
int lastOne = left;
int firstZero = right;
int pos;
while(firstZero - lastOne > 1) {
pos = (lastOne + firstZero) / 2;
if(pos) {
lastOne = pos;
} else {
firstZero = pos;
}
}
return firstZero;
}
int sumOnes(int **map) {
int sum = 0;
for(int i = 0; i < N; i++) {
sum += findFirstZero(map[i], i, N-i-1);
}
return sum;
}
Now, this is actually O(NlogN), but given the constraints of the problem as I understand them, I'm quite certain that's the best possible; either you or Cormen left something out of the problem or Cormen made a mistake in his big-O analysis. I'd love to see a proof to the contrary, though.