Easy Problem

Thought Process

The Easy Problem requires finding the number of ways to represent a given number 'n' as a sum of two positive integers. Here are two approaches:

Approach 1: Brute Force - Use nested loops to iterate through all possible pairs of positive integers (i, j) such that i + j = n. Count the number of valid pairs and print the result.

Approach 2: Mathematical Optimization - Since the problem involves finding the number of ways to represent 'n' as a sum of two positive integers, we can directly calculate the result as n - 1. This is because for any number 'n', there are exactly n - 1 pairs of positive integers that sum up to 'n'.

Approach 1: Brute Force

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int n;
    int cnt = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if ((i + j) == n)
                cnt++;
        }
    }
    cout << cnt << endl;
}

int main()
{
    int testCases;
    cin >> testCases;
    while (testCases--)
    {
        solve();
    }
}

Approach 2: Mathematical Optimization

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int n;
    cin >> n;
    cout << n - 1 << endl;
}

int main()
{
    int testCases;
    cin >> testCases;
    while (testCases--)
    {
        solve();
    }
}

Code Complexity

Time Complexity: O(n²) & O(1)

Approach 1 uses nested loops, resulting in quadratic time complexity, while Approach 2 calculates the result in constant time.

Space Complexity: O(1)

Both approaches use constant extra space, making them highly efficient.

C++: Easy Problem