Member Avatar for warpstar

Heres the problem, Ill try my best to explain this: If your given a 5x5 array whicih looks like:

1 1 1 1 1
0 1 1 1 1
0 0 1 1 1
0 0 0 0 1
0 0 0 0 0

Basically in each column below any 1 is a set of zeros. What they want us to do is create a new array which will store the position where u hit ones in each ROW. For the example above it would be like

1
2
3
5
6 (if its all zeroes then we just assume after 6 zeros it would hit a 1)

So this array (1,2,3,5,6) would be printed on the screen. Any idea how i would do this? This is a sample midterm question which is not worth any marks so please if you can put any code watsoever will help.

  • 3 Contributors
  • 3 Replies
  • 108 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by warpstar

Dani AI

Generated

The sample output uses 1-based column positions and treats a row with no 1 as "m+1" (for a 5x5 grid that becomes 6). That is a sentinel value, not a real column index. Choose whatever sentinel fits the spec you were given (0, -1, or m+1) and be consistent.

As pointed out, scanning each row until you hit the first 1 works and is simple (O(n*m)). If the matrix has the staircase property your example shows — the first-1 column never moves left as you go down the rows (the first-1 indices are nondecreasing) — you can do better. Keep a single column pointer that only moves right across all rows. For each row advance that pointer until you see a 1; record column+1 (or m+1 if you run off the right). The pointer increments at most m times overall, so total work is O(n + m).

Example C++ sketch (adjust input/filling of grid to your case):

#include <vector>
#include <iostream>

int main() {
    int n = /* rows */, m = /* cols */;
    std::vector<std::vector<int>> grid(n, std::vector<int>(m)); // fill with 0/1
    std::vector<int> pos(n, m+1); // default sentinel m+1 (1-based)
    int col = 0;
    for (int row = 0; row < n; ++row) {
        while (col < m && grid[row][col] == 0) ++col;
        pos[row] = (col < m ? col + 1 : m + 1);
    }
    for (int v : pos) std::cout << v << '\n';
}

Cautions: this optimized scan only works when first-1 positions do not decrease between rows. If that property is not guaranteed, reset col to 0 for each row (or use the simple nested-loop scan). Watch off-by-one choices (0-based storage vs. 1-based output) and pick a clear sentinel.

Recommended Answers

All 3 Replies

Member Avatar for Member #46692

No! Do your own homework or provide some code you have tried for us to look at.

Member Avatar for twomers

It's a 2-D array, presumably. Start from the top and go along each row and record the position of the first one.

Pseudo code:

loop y=0, 5
  loop x=0, 5
    if val of array[y][x] is 1
      print (x+1)
      break loop
  end loop x
end loop y
Member Avatar for warpstar

Thanks alot twomers!

It's a 2-D array, presumably. Start from the top and go along each row and record the position of the first one.

Pseudo code:

loop y=0, 5
  loop x=0, 5
    if val of array[y][x] is 1
      print (x+1)
      break loop
  end loop x
end loop y
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.