Java: 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 

import java.util.Scanner;
    
public class CF {
    
    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        int testCases = sc.nextInt();
        while (testCases > 0) {
            int cnt = 0;
            int target = sc.nextInt();
            for (int i = 1; i <= 100; i++) {
                for (int j = 1; j <= 100; j++) {
                    if ((i + j) == target)
                        cnt++;
                }
            }
            System.out.println(cnt);
            testCases--;
        }
    }
}

Approach 2: Mathematical Optimization 

import java.util.Scanner;

public class CF {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int testCases = sc.nextInt();
        while (testCases > 0) {
            int cnt = 0;
            int target = sc.nextInt();
            System.out.println(target-1);
            testCases--;
        }
    }
}

Code Complexity

Time Complexity: O(n2) & 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.

Code copied!