How to generalize if-else tree using a loop?

Question

I am trying to print the following pattern:

n = 2   n = 5            

2 2 2   5 5 5 5 5 5 5 5 5 
2 1 2   5 4 4 4 4 4 4 4 5 
2 2 2   5 4 3 3 3 3 3 4 5 
        5 4 3 2 2 2 3 4 5 
        5 4 3 2 1 2 3 4 5 
        5 4 3 2 2 2 3 4 5 
        5 4 3 3 3 3 3 4 5 
        5 4 4 4 4 4 4 4 5 
        5 5 5 5 5 5 5 5 5

This is what I have tried which works for n = 1,2,3

Code Snippet:

#include <iostream>

using std::cout;
using std::cin;

int main()
{
    int n,m;
    cin>>n;
    m = 2*n - 1;
    int **arr = new int*[m];
    for(int i = 0; i < m; i++)
        arr[i] = new int[m];

    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(i == 0 or j == 0 or i == m - 1 or j == m - 1)
                arr[i][j] = n;
            else    if (i == 1 or j == 1 or i == m - 2 or j == m - 2)
                arr[i][j] = n - 1;
            else
                arr[i][j] = 1;
        }
    }
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cout<<arr[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

For other inputs I need to generalize the if-else tree using a loop. I tried using the following snippet,

for(int k = 0; k < m; k++)
    if(i == k or j == k or i == m - k - 1 or j == m - k - 1)
        arr[i][j] = n - k;

Output for n = 2:

0 0 0
0 1 0
0 0 0

Update: Based on the first code snippet, what I understand is the for loop in the second code snippet is missing the else part.

1. Please remove that bits/stdc++ include. 2. Avoid using namespace std; 3. Use a debugger to find out where the problem lies. — Michael Chourdakis, Jul 12 '19 at 17:41
Unrelated: `#include` [loads the gun](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). `using namespace std;` [takes the safety off](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). Be really careful. — user4581301, Jul 12 '19 at 17:42
It is often very informative to see what the unexpected behaviour is. You should add the output of the program to the question along with whatever you learn from the debugger. — user4581301, Jul 12 '19 at 17:43
For purposes of competitive programming, I used ```bits/stdc++``` header file and ```namespace std```, however I do realize that it's not good practice. Also regarding debugging the program, I did manually trace it however I realized now that the for loop did not break once it found the right condition for the indices. Thank you all for your help. — Saurabh P Bhandari, Jul 13 '19 at 11:29

score 1 · Answer 1 · edited Jul 12 '19 at 18:39

For such tasks it is vital that you recognize patterns and play a bit with math.

If you subtract n from every number in your output, it becomes the distance to the nearest border. This distance is for any pair of iteration indices (i, j) either i, m-i, j, or m-j.

Using this information, you can come up with a fairly simple code:

#include <iostream>
#include <algorithm>

int main()
{
    int n;
    std::cin >> n;
    n = 2*n - 1;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            // Distance to x border
            int ii = std::min(i, n - i - 1);
            // Distance to y border
            int jj = std::min(j, n - j - 1);
            // Distance to any one of the two
            int d = std::min(ii, jj);

            std::cout << n/2-d + 1 << ' ';
            //           ^^^^^^^^^ Make the outside large and the inside small
        }
        std::cout << std::endl;
    }
}

Wyck · Answer 2 · 2019-07-13T00:47:56.570

I suggest a completely different approach. The number at each position can be directly computed based on its coordinates using a simple function. max(|dx|,|dy|)

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <cstdlib>

std::string box(int n) {
    std::stringstream s;
    int m = n - 1;
    for (int y = -m; y <= m; ++y) {
        for (int x = -m; x <= m; ++x) {
            s << (std::max(std::abs(x),std::abs(y)) + 1) << ' ';
        }
        s << std::endl;
    }
    return s.str();
}

int main()
{
    std::cout << box(2);
    std::cout << box(5);
    return 0;
}

Run the above code online

Or run it right here (in JavaScript)

function box(n) {
  var str = '';
  var m = n - 1;
  for (var y = -m; y <= m; ++y) {
    for (var x = -m; x <= m; ++x) {
      var d = Math.max(Math.abs(x), Math.abs(y)) + 1;
      str += d + ' ';
    }
    str += '\n';
  }
  return str;
}


console.log(box(2));
console.log(box(5));

Your example is not in C++. The `var` is a syntax error, as well as `function` and lack of return type. — Thomas Matthews, Jul 12 '19 at 19:58

score 0 · Accepted Answer · answered Jul 13 '19 at 11:26

0

Thank you everyone, for your answers, Silly me, I was just missing a break statement.

for(int k = 0; k < m; k++)
{
    if(i == k or j == k or i == m - k - 1 or j == m - k - 1)
    {
        arr[i][j] = n - k ;
        break;
    }
}

answered Jul 13 '19 at 11:26

Saurabh P Bhandari

6,014
1
19
50

Please note that it is not an efficient solution in terms of time complexity, as it has 3 for loops so the time complexity turns out to be ```O(n^3)```, refer to other answers for better time and space complexity – Saurabh P Bhandari Jul 13 '19 at 11:32

How to generalize if-else tree using a loop?

3 Answers3