# diagonal elements in a matrix - challenge - not a h/w

Page 1 of 1

## 7 Replies - 1187 Views - Last Post: 24 March 2017 - 08:40 AM

### #1 uniqCoder

Reputation: 4
• Posts: 67
• Joined: 13-March 16

# diagonal elements in a matrix - challenge - not a h/w

Posted 16 October 2016 - 11:27 AM

This is a very beginner level question.

Just print the diagonal elements in a given matrix....but it should be the best efficient one.

I was doing it in a very inefficient way until I got an instinct to do it better.

Spoiler

I have the wisdom that I don't want to steal from anyone.

Is This A Good Question/Topic? 0

## Replies To: diagonal elements in a matrix - challenge - not a h/w

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12134
• Posts: 45,117
• Joined: 27-December 08

## Re: diagonal elements in a matrix - challenge - not a h/w

Posted 16 October 2016 - 11:36 AM

The solution is really obvious. I don't see the point for discussion here. There aren't other approaches to this, besides the obvious one and the inefficient one.

### #3 uniqCoder

Reputation: 4
• Posts: 67
• Joined: 13-March 16

## Re: diagonal elements in a matrix - challenge - not a h/w

Posted 16 October 2016 - 11:40 AM

Ok...I see so many experts here...this was meant to be a.beginner level problem

I havehave to lean more.

### #4 Skydiver

• Code herder

Reputation: 5824
• Posts: 19,835
• Joined: 05-May 12

## Re: diagonal elements in a matrix - challenge - not a h/w

Posted 16 October 2016 - 01:46 PM

Assuming a contiguous two dimensional square matrix in C or C++, there is actually something more efficient. It'll have the same O(n) complexity, but the cost of each iteration involves simple addition rather than the usual multiplication and addition done when doing two dimensional indexing, or the indirection and offsetting that a naïve compiler may implement.

### #5 Skydiver

• Code herder

Reputation: 5824
• Posts: 19,835
• Joined: 05-May 12

## Re: diagonal elements in a matrix - challenge - not a h/w

Posted 18 October 2016 - 05:40 AM

LOL! This is going to abuse hashtables, but if you set things up just right, you could have all the elements on the diagonal to all hash to the same key. Since people claim that hashtables have amortized/average O(1) access even if they use chaining, you could claim that you are getting O(1) to list N elements.

Other people will say: "But wait! That's apples and oranges!" Unfortunately, the going wisdom is that hashtables are treated as O(1) even if they use chaining or probing because when they compute the complexity of hashtables they only look at the average case, while looking at the complexity of everything else, they look at the worse case.

### #6 #define

• Duke of Err

Reputation: 1850
• Posts: 6,646
• Joined: 19-February 09

## Re: diagonal elements in a matrix - challenge - not a h/w

Posted 20 October 2016 - 08:42 PM

uniqCoder your discovery is to be admired. The efficiency has increased in the use of flops as well as in code input. Don't let the gigantic boots of jaded grandee Dics, who have forgotten or disregard the joie de codage of earlier years, squash your delight.

```Little Jack Horner
Sat in the corner,
Programming the value of pi;
He put in his num,
And pulled out a sum,
And said 'What a good coder am I!'
```

### #7 jjl

• Engineer

Reputation: 1265
• Posts: 4,979
• Joined: 09-June 09

## Re: diagonal elements in a matrix - challenge - not a h/w

Posted 08 November 2016 - 06:36 PM

Like skydiver mentioned, you could avoid the 2D array indexing overhead by using a 1D array. This would effectively save N multiplications.

```int index = 0;
for(int i=0; i < N; ++i) {
std::cout<<matrix[index];
index += N + 1;
}

```

The memory reads are also non-coalesced accesses since you are on a diagonal. There may be some optimization in that department, but that would involve restructuring the matrix.

### #8 IngeniousHax

• |>|20-514<|{3|2

Reputation: 84
• Posts: 1,385
• Joined: 28-March 09

## Re: diagonal elements in a matrix - challenge - not a h/w

Posted 24 March 2017 - 08:40 AM

You can also use pointer arithmetic to accomplish this. Although a bit more difficult to read...
```    for(int i = 0; i < HEIGHT; i++)
{
printf("%d\n", *(*(matrix + i) + i));
}

```

This post has been edited by IngeniousHax: 24 March 2017 - 08:41 AM

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }