18

Consider:

Enter image description here

I am trying to find the area of an n-interesting polygon, where (n=1, A=1, n=2, A=5, n=3, A=13, n=4, A=25, and so on). So the formula for an n-interesting polygon is the area of an (n-1)-interesting polygon+(n-1)*4. When running the program, a hidden test shows that the code is wrong. What is wrong with my code?

def shapeArea(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    for i in range(2, n+1):
        return (shapeArea(n-1) + (n-1)*4)
6
  • Why you need for loop? It useless, it will never come far then i==2. What's the exact formula for area? The formula in your code gives 13 for n=3, not 8, but 25 for 4...
    – Amaro Vita
    Mar 14, 2018 at 5:36
  • In that case, there's nothing wrong with your code.
    – Aran-Fey
    Mar 14, 2018 at 5:45
  • 2
    Рrobably the hidden test calls your function with some large number and is terminated because of a timeout or stack limit. Try to find an explicit formula for shapeArea(n) that does not use recursion. shapeArea(1000) already fails on my machine. Mar 14, 2018 at 6:08
  • @DmitriChubarov I think that was the problem.
    – M-M
    Mar 14, 2018 at 6:26
  • If n=1, you need to return a 1 for control statement on line 2, "if n==0" for the recursive call; otherwise, you'll return an area of 0. The for loop is unnecessary, but shouldn't cause any real issue. Jun 13, 2020 at 23:53

21 Answers 21

32

As there are already coding examples, I will explain why the formula is n * n + (n-1) * (n-1)

  1. You need to see the graph diagonally
  2. You will notice that the sides are always n
  3. For example, if n=4, the shape has for 4 squares on each side, thus n * n
  4. However, if you notice, n * n does not account for all the squares. There are squares in between the once you accounted for
  5. Take away the square you have accounted with n * n, you will notice now that the side of the shape is now n-1
  6. Thus, you take into account of the squares in between, the formula is n * n + (n-1) * (n-1)
  7. Example: if n = 4, the outer square is 4 * 4 = 16. Then take away the area you have just calculated, the inner squares is 3 * 3 = 9. Add together, you get 25.
3
  • 1
    Thank you for your explanation! This makes it easier to understand the solution!
    – flopperJ
    May 30, 2021 at 5:48
  • 6
    this youtube videos has a excellent visual explanation of why that is the correct formula: youtu.be/zKrDTVsQ-F4?t=796
    – Nei
    Nov 18, 2021 at 17:04
  • @Nei You're right. This is so much better than my wall of text trying to get readers to visualise.
    – ProFire
    Nov 19, 2021 at 18:51
31

I found the formula without the recursion. The test went through fine.

def shapeArea(n):
    if n>=10**4 or n<1:
        return False

    return (n**2+(n-1)**2)
3
  • 8
    Would you kindly explain how you came to this formula? It worked for me, but I'd like to understand why.
    – Z41N
    Jul 7, 2020 at 15:37
  • how did you come up with? The Formula: n^2+(n-1)^2
    – avatarZuko
    Feb 12, 2021 at 19:31
  • 5
    @Z41N It's pretty easy visually if you split the figure into quadrants, centred next to the central square: you end up with four differently sized "triangles", where the biggest two can be joined to form n² and the smallest two can be joined to form (n-1)².
    – l0b0
    Feb 17, 2022 at 4:34
10

The easiest solution to the problem in JavaScript:

function shapeArea(n) {
    if(n<0) {
        return false
    }
    return (n*n) + ((n-1)*(n-1))
}

console.log(shapeArea(1))
1
8

I think the last part where you have written the 'for' loop is dodgy. If you're already using recursion why do you need a 'for' loop? Nonetheless, I did it this way without using recursion:

def shapeArea(n):
    if n == 1:
        return 1
    return n**2 + (n-1)**2
1
  • This is not valid Python code. Can you fix it? (But without "Edit:", "Update:", or similar - the question/answer should appear as if it was written today.) Feb 8, 2022 at 11:39
6

Here's an approach one can use to derive a formula.

The shapes always have a horizontal line across the middle. If you draw a rectangle that emcompasses both the top square and the horizontal line, there will always be a void of white squares within it large enough to be partially filled by the squares below the line.

Imagine that you fill that void above the line with the squares below the line. With the exception of n=1, your shape will be changed to a rectangle that still has some white squares in it. Let's look at a few.

n=2                n=3                         n=4

. X .   X X .      . . X . .    X X X . .      . . . X . . .    X X X X . . .
X X X   X X X      . X X X .    X X X X X      . . X X X . .    X X X X X X X
. X .   . . .      X X X X X    X X X X X      . X X X X X .    X X X X X X X
                   . X X X .    . . . . .      X X X X X X X    X X X X X X X
                   . . X . .    . . . . .      . X X X X X .    . . . . . . .
                                               . . X X X . .    . . . . . . .
                                               . . . X . . .    . . . . . . .

The new shape can be characterized with the formula: area = height * width - gap

If we chart that out to look for patterns, it looks like this:

n | height | width | gap
1 |    1   |   1   |  0
2 |    2   |   3   |  1
3 |    3   |   5   |  2
4 |    4   |   7   |  3

Both height and gap are counting by one, and width is skip-counting by 2. You can always characterize that linear trend as n*skipValue +/- constant. In this case,

height=n
width=2n-1
gap=n-1

Plugging those terms back into our formula for the area of the gapped rectangles,

area = height * width - gap becomes area = n * (2n - 1) - (n - 1)

3

This may be a solution:

function shapeArea(n) {
    return ((n-1) * (n*2)) + 1;
}
3
  • 2
    I say that it is insufficiently explained and is therefor not convincing enough to be upvoted. Also, I recommend against rhetoric questions in answer posts, because the often get misunderstood as asking a clarification question, which risks having them flagged and deleted as not being an answer.
    – Yunnosch
    Jun 24, 2021 at 10:15
  • What programming language? C#? Java? JavaScript? Something else? Feb 8, 2022 at 11:59
  • nice precise answer
    – MMH
    Jul 25, 2022 at 9:26
2
def shapeArea(n):
  if n == 1:
    return 1
  square_side = n+n-1
  outer_square_area = square_side**2
  white_pieces = 4*(1/2)*n*(n+1)
  area = outer_square - white_pieces
  return area

A different approach to the problem:

If you notice, each n-interesting polygon can be contained in a surrounding square that has sides of length 2n-1. One could take this "outter square" and subtract the area of the missing white spaces.

Coming up with a formula for the white pieces is tricky because you have to add up these weird stair-step-like pieces on each of the 4 sides. The area for these weird pieces can actually be calculated using the formula for consecutive integers or 1/2*N(N+1) (For this problem N=n-1)

This can easily be seen for for the n=2, the larger surrounding square side is 2+(2-1)=3 so the total area will be 9 - 4 = 5.

To better understand how the connection to how the white area is calculated see the visualization behind the formula. Notice how counting the area of these triangular blocks is similar to adding up integers from 1...n

1

This is a formula to find an area of polygon for given n

def shapeArea(n):
    return (n**2)+((n-1)**2)

shapeArea(3)

Output

13
1

Like an alternative, I found a solution using a for loop.

def shapeArea(n):
    return sum([( num * 4 ) for num in range(1, n)]) + 1
1

This passed all the tests without performance issues:

def IncreasingSequence(sequence):
  for x in range(0, len(sequence) - 1):
    if sequence[y] >= sequence[x + 1]:
        alt1 = sequence.copy()
        alt2 = sequence.copy()

        alt1.pop(x)
        alt2.pop(x+1)

        return (False, alt1, alt2)

  return (True, sequence, sequence)

def almostIncreasingSequence(sequence):
  boo, nl1, nl2 = IncreasingSequence(sequence)
  if boo == False:
    boo1, ll, ll1 = IncreasingSequence(nl1)
    if boo1 == False:
        boo2, l1, l2 =IncreasingSequence(nl2)
        return boo2
  return True
1
  • Is this valid Python code? The indentation is not consistent. Using Python 3.8.10 on Ubuntu MATE 20.04: IndentationError: unexpected indent Feb 8, 2022 at 11:46
1

Use:

def shapeArea(n):
    sum = 0
    i = 1
    while(n>1):
        sum = sum + 2*i
        n = n - 1
        i = 2 + i
   sum = sum + i
   return sum

Try to calculate the sum of row wise squares (twice 2*i) and add the middle row at the end.

1

An easy-to-understand solution in Ruby without recursion:

def shapeArea(n)
    total = 0
    (1..n-1).each do |column|
       total += column + (column-1)
    end
    (total*2) + (n+(n-1))
end
  • Both sides will have equal amounts of squares, except the center column that does not repeat. So we calculate the sides using the (1..n-1) loop, and the number of squares will be always column + (column - 1);
  • After that we just need to multiply this by 2 to get the sum of both sides (total*2) and add the center column (n+(n-1)).
1

This works (Python 3):

def shapeArea(n):
    area = n*n + (n-1)*(n-1)
    return area

print(shapeArea(5))
0

For C#, use this code:

if (n == 0) {
    return 0;
}
if (n == 1) {
    return 1;
}
return Convert.ToInt32(Math.Pow((2*n - 1),2) - 2 * n * (n - 1));
// Math.Pow is used to calculate a number raise to the power of some other number
1
  • Return a value from what? Isn't something missing? Feb 8, 2022 at 11:52
0

If we see the given example,

when n=1, poly = 1

when n=2, poly = 5

when n=3, poly = 13

when n=4, poly = 25

the next pattern could be found by formula 2n(n-1) + 1:

def shapeArea(n):
    return 2 * n * (n - 1) + 1;
3
  • Please include an explanation
    – mousetail
    Oct 6, 2021 at 9:11
  • if you see the given example, when n=1, poly = 1, when n=2, poly = 5, when n=3, poly = 13, when n=4, poly = 25. so the next pattern could be find by formula 2*n*(n-1)+1. Oct 7, 2021 at 3:54
  • 1
    Please edit your post, don't post as a comment
    – mousetail
    Oct 7, 2021 at 9:01
0

In Python:

In every increasing n, the 4's table is added to the previous one's polygon number:

def solution(n):
    if n == 1:
        return 1
    else:
        c = 0
        for i in range(1, n):
            c += 4*i
    return c + 1
0

I initially read the problem wrong. I thought we need to find the outside edges.

Let's first see how we can do that...and then it will lead to a more intuitive solution later for this problem.

For the number of edges, I was looking at the outermost diagonal and see 2*(n-1) edges on each of the four diagonals. It doesn't include the main four edges which are also present when n = 1.

So the total number of edges is (4 + 4 * 2 * (n-1))

Note that since we do not want to calculate number of edges, but the area, we will only use n-1 for the area rather than 2 * (n-1).

Also, we need to subtract one since we were looking at outer edges...or how many additional squares the next iteration will need...so we will use (n-1)-1

Now let’s use this to calculate the area:

n = 1 is 1
n = 2 we need to add 4 + 4* ((n-1)-1) squares or 4 + 4 * (n-2) squares
n = 3 we need to add an additional 4 + 4 * (n-2) squares
n = 4 we need to add an additional 4 + 4 * (n-2) squares
if n == 1:
    return 1

area = 1

for n in range (1, n+1):
   area += 4 + 4*(n-2)

return area
0

How can we find the formula if we don't see the partitioning trick? The definition f(1) = 1; f(n) = f(n-1) + 4*n for n > 1 relates an area to a length. We may therefore hypothesize that f(n) is quadratically related to n: a*n*n + b*b +c. We can determine the coefficients algebraically from the first 3 pairs: f(1) = 1, f(2) = 5, f(3) = 13, which give us 3 equations in 3 unknowns:

a + b + c = 1
4a + 2b + c = 5
9a + 3b + c = 13

Eliminating c = 1 - a - b first, we get

3a + b = 4
8a + 2b = 12

Eliminating b = 4 - 3a next, we get

2a = 4

Hence a = 2, b = -2, c = 1, so f(n) = 2*n*(n-1) + 1. We can verify by induction.

Note: Getting the formula for the sum of counts, f(0) = 0; f(n) = f(n-1) + n for n > 0, is even simpler because the first equation is c = 0. The remaining pair

a + b = 1
4a + 2b = 3

is easily solved to get a = b = 1/2, giving f(n) = n*(n+1)/2.

0
/**
Break down: 

1= 1.     1 + 0
2 = 5.    1 + 4
3 = 13.    5  + 8
4 = 29    13 + 16
5 = 49      29 + 20 

**/

int solution(int n) {
    int area = poly(n);
    System.out.println(area);
    return area;
}

int poly(int n){
    if(n == 1 ){
        return 1;
    }
    else{
        return poly(n-1) + side(n); 
    }
}
int side(int n){
    if(n == 1 ){
        return 0;
    }
    else{
        return (n-1) * 4;
    }
}
0

These worked fine for me.

n*n + (n-1) * (n-1)

n * (2*n - 1) - (n-1)
0
int solution(int n) {
    int nSquared = n * n;
    int nTimesTwo = n * 2; 
    int leadingCoeficient = nSquared * 2;
    int area = 0;
    if (n == 1) {
        area = n;
    } else if (n == 2){
        area = 5;
    } else {
        area = (leadingCoeficient-nTimesTwo)+1;
    }
    return area;
}

Not the answer you're looking for? Browse other questions tagged or ask your own question.