Original Problem


  • The idea here is that the perimeter of a rectangle must be an even number 2k, where k is an Integer (整数). Because there are 2 pairs of height+width which is k to fit into the definition of even number
  • Thus, we can return 0 straight if n%2 == 1
  • Otherwise, we can obtain k by dividing the given n by 2
  • Remember k is height+width, so if k is 10, the possible combination of height and width is (1,9), (2,8), (3,7), (4,6) and (5,5)
  • We not including (6,4) because it is same as (6,4). The order doesn’t matter
  • We can observe that after the midpoint 5, it starts to repeat itself
  • So we can conclude that the possible combination of height and width given k is k/2 (rounding down)
  • Since we don’t want square, which means the height and width are the same (5,5), k=10, and this can only happen when k%2 = 0 aka k can be split into 2 equal values
  • Thus, we minus 1 to the final answer if k%2 = 0

Space & Time Analysis

The analysis method we are using is Algorithm Complexity Analysis

Space - O(1)

  • Ignore input size & language dependent space
  • We aren’t creating any objects on the Heap Segment

Time - O(1)

  • No looping is needed to loop through all possible pairs of height and width by leveraging on the beauty of counting


1st Attempt (Java)

import java.util.Scanner;
public class Solution {
  public static void main(String[] args) {
    // Read input data
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int res = 0;
    if (n % 2 == 1) {
    int widthHeight = n/2;
    res = widthHeight/2;
    if (widthHeight % 2 == 0) res--;

Personal Reflection

  • Why it takes so long to solve: simply unfamiliar with combinatorics and failed to make basic deduction that the perimeter of rectangle must be even
  • What you could have done better: Practice more combinatorics and read about counting in Discrete Math
  • What you missed: perimeter of rectangle must be even and using counting to come out an answer in constant time instead of loop through each possible pair of height and width
  • Ideas you’ve seen before: the definition of even number, 2k where k is an Integer (整数)
  • Ideas you found here that could help you later: the beauty of counting in combinatorics
  • Ideas that didn’t work and why: Looping through each possible pair of height and width. This takes linear time and it leads to timeout