Skip to main content

Math Basics

Find the AP/GP/HP Solution In C++/Java/Python/JS

When preparing for DSA interviews, we often come across number sequences. Three common types are:

  • Arithmetic Progression (AP) – where the difference between consecutive terms is constant.
  • Geometric Progression (GP) – where the ratio between consecutive terms is constant.
  • Harmonic Progression (HP) – where the reciprocals of the terms form an AP.
Understanding these sequences is essential for mathematical problem-solving, algorithm design, and real-world applications like finance, physics, and engineering. Let's explore each of these in-depth with step-by-step learning, intuition building, and problem-solving strategies.

1. Arithmetic Progression (AP)

Description

An Arithmetic Progression (AP) is a sequence of numbers where the difference between any two consecutive terms is the same. This difference is called the common difference (d).

Mathematical Representation

If the first term is a and the common difference is d, then the AP looks like:

a, a + d, a + 2d, a + 3d, ...

The n th term of an AP is given by:

Tn = a + (n-1) * d

The sum of the first n terms is:

S = n/2 * (2a + (n-1) * d)

This formula allows us to quickly compute terms and sums instead of iterating through the sequence manually.

Example

Consider this sequence:

3, 7, 11, 15, 19

Here, the common difference is: d = 7 - 3 = 4

The 10th term would be:

T10 = 3 + (10-1) * 4 = 3 + 36 = 39

Find if the Given Array is in AP

Intuition

If we are given an array, how do we check if it follows AP? We need to ensure every term maintains a fixed difference with the previous term.

Algorithm

  1. Compute d = arr[1] - arr[0].
  2. Loop through the array and check if arr[i] - arr[i-1] == d.
  3. If true for all terms, the array follows AP.

Real-World Example

  • AP is used in simple interest calculations in finance.
  • Used in sequence numbering systems, like seat numbers in theaters or bus tickets.

Similar Questions

  • Find missing terms in an AP.
  • Find sum of first n terms in an AP.

2. Geometric Progression (GP)

Description

A Geometric Progression (GP) is a sequence where each term is obtained by multiplying the previous term by a fixed common ratio (r).

Mathematical Representation

a, a*r, a*r^2, a*r^3, ...

The n th term of a GP is given by:

Tn = a * r^(n-1)

The sum of the first n terms is:

S = a * (1 - r^n) / (1 - r)

(when r != 1)

Example

Consider this sequence:

2, 6, 18, 54, 162

Here, the common ratio is:

r = 6 / 2 = 3

The 6th term would be:

T6 = 2 * 3^(6-1) = 2 * 243 = 486

Find the GP of a Given Array

Intuition

To check if a sequence follows GP, we need to ensure each term is a constant multiple of the previous term.

Algorithm

  1. Compute r = arr[1] / arr[0].
  2. Loop through the array and check if arr[i] / arr[i-1] == r.
  3. If true for all terms, the array follows GP.

Real-World Example

  • GP is used in compound interest calculations where interest compounds over time.
  • Used in exponential growth models like population growth and bacterial reproduction.

Similar Questions

  • Find the missing term in a GP.
  • Find the sum of the first n terms in a GP.

3. Harmonic Progression (HP)

Description

A Harmonic Progression (HP) is a sequence where the reciprocals of the terms form an Arithmetic Progression (AP).

Mathematical Representation

If the given sequence is:

a1, a2, a3, a4, ...

Then, their reciprocals must form an AP:

1/a1, 1/a2, 1/a3, 1/a4, ...

The n th term of an HP is:

Tn = 1 / (a + (n-1) * d)

Example

Consider this sequence:

1, 1/2, 1/3, 1/4, 1/5

The reciprocals are:

1, 2, 3, 4, 5

which forms an AP with d = 1.

Find the HP of a Given Array

Intuition

To check if an array follows HP, we need to first convert it into an AP by taking reciprocals and then apply the AP approach.

Algorithm

  1. Compute reciprocals of all elements.
  2. Check if they form an AP using the AP approach.

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n) (due to storing reciprocals)

Real-World Example

  • HP is used in physics for resistance in parallel circuits.
  • Used in computer science for load balancing algorithms where tasks are divided inversely to processing speeds.

Similar Questions

  • Convert an HP to an AP.
  • Find missing terms in an HP.
Since, we have explored what an AP,GP and HP are. Now, let's how we can implement the logic in Java, C++, Python and JavaScript and then analyse the time, auxiliary space and total space complexity.

Find the AP/GP/HP of a given Array Algorithm

1. Checking if the sequence is an Arithmetic Progression (AP)

  • Compute the common difference d = arr[1] - arr[0].
  • Iterate through the array from index 2 to n-1:
    • If arr[i] - arr[i-1] != d, return false (not an AP).
  • If all terms satisfy the AP rule, return true (sequence is an AP).

2. Checking if the sequence is a Geometric Progression (GP)

  • Compute the common ratio r = arr[1] / arr[0].
  • Iterate through the array from index 2 to n-1:
    • If arr[i] / arr[i-1] != r, return false (not a GP).
  • If all terms satisfy the GP rule, return true (sequence is a GP).

3. Checking if the sequence is a Harmonic Progression (HP)

  • Convert the sequence into its reciprocal:
    • Create a new array reciprocal[] where reciprocal[i] = 1.0 / arr[i].
  • Check if reciprocal[] forms an AP using a helper function:
    • Compute d = reciprocal[1] - reciprocal[0].
    • Iterate through the array from index 2 to n-1:
      • If reciprocal[i] - reciprocal[i-1] != d, return false (not an HP).
    • If all terms satisfy the AP rule, return true (sequence is an HP).

Solution

Now, let's see how we can code it up.

"Find the AP/GP/HP of a given Array" Code in all Languages.
1. Find the AP/GP/HP of a given Array Solution in C++ Try on Compiler 
#include <iostream>
using namespace std;

// Function to check if the given sequence is an Arithmetic Progression (AP)
bool isAP(int arr[], int n) {
    
    int d = arr[1] - arr[0];

    for (int i = 2; i < n; i++) {
        if (arr[i] - arr[i - 1] != d) {
            return false;
        }
    }
    return true;
}

// Function to check if the given sequence is a Geometric Progression (GP)
bool isGP(int arr[], int n) {
    
    double r = (double) arr[1] / arr[0];

    for (int i = 2; i < n; i++) {
        if ((double) arr[i] / arr[i - 1] != r) {
            return false;
        }
    }
    return true;
}

// Function to check if the given sequence is a Harmonic Progression (HP)
bool isHP(int arr[], int n) {
    
    double reciprocal[n];

    for (int i = 0; i < n; i++) {
        reciprocal[i] = 1.0 / arr[i];
    }

    return isAP(reciprocal, n);
}

int main() {
    
    int n;
    
    cout << "Enter number of elements: ";
    cin >> n;
    
    int arr[n];

    cout << "Enter elements: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    cout << (isAP(arr, n) ? "The sequence is an AP\n" : "Not an AP\n");
    cout << (isGP(arr, n) ? "The sequence is a GP\n" : "Not a GP\n");
    cout << (isHP(arr, n) ? "The sequence is an HP\n" : "Not an HP\n");

    return 0;
}

2. Find the AP/GP/HP of a given Array Solution in Java Try on Compiler 
import java.util.Scanner;

class ProgressionModules {

    // Function to check if the given sequence is an Arithmetic Progression (AP)
    public static boolean isAP(int[] arr) {
        
        // Compute common difference
        int d = arr[1] - arr[0];

        // Check if every term follows the AP rule
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] - arr[i - 1] != d) {
                return false;
            }
        }
        return true;
    }

    // Function to check if the given sequence is a Geometric Progression (GP)
    public static boolean isGP(int[] arr) {
        
        // Compute common ratio
        double r = (double) arr[1] / arr[0];

        // Check if every term follows the GP rule
        for (int i = 2; i < arr.length; i++) {
            if ((double) arr[i] / arr[i - 1] != r) {
                return false;
            }
        }
        return true;
    }

    // Function to check if the given sequence is a Harmonic Progression (HP)
    public static boolean isHP(int[] arr) {
        
        // Convert to reciprocal and check if it forms an AP
        double[] reciprocal = new double[arr.length];

        for (int i = 0; i < arr.length; i++) {
            reciprocal[i] = 1.0 / arr[i];
        }

        return isAPDouble(reciprocal);
    }

    // Helper function to check if a double array forms an AP
    public static boolean isAPDouble(double[] arr) {
        
        double d = arr[1] - arr[0];

        for (int i = 2; i < arr.length; i++) {
            if (arr[i] - arr[i - 1] != d) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        System.out.print("Enter number of elements: ");
        int n = sc.nextInt();
        
        int[] arr = new int[n];

        System.out.println("Enter elements: ");
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println(isAP(arr) ? "The sequence is an AP" : "Not an AP");
        System.out.println(isGP(arr) ? "The sequence is a GP" : "Not a GP");
        System.out.println(isHP(arr) ? "The sequence is an HP" : "Not an HP");
    }
}

3. Find the AP/GP/HP of a given Array Solution in Python Try on Compiler 
# Function to check if the given sequence is an Arithmetic Progression (AP)
def is_ap(arr):
    
    d = arr[1] - arr[0]

    for i in range(2, len(arr)):
        if arr[i] - arr[i - 1] != d:
            return False
    return True

# Function to check if the given sequence is a Geometric Progression (GP)
def is_gp(arr):
    
    r = arr[1] / arr[0]

    for i in range(2, len(arr)):
        if arr[i] / arr[i - 1] != r:
            return False
    return True

# Function to check if the given sequence is a Harmonic Progression (HP)
def is_hp(arr):
    
    reciprocal = [1.0 / x for x in arr]

    return is_ap(reciprocal)

if __name__ == "__main__":
    
    arr = list(map(int, input("Enter elements separated by space: ").split()))

    print("The sequence is an AP" if is_ap(arr) else "Not an AP")
    print("The sequence is a GP" if is_gp(arr) else "Not a GP")
    print("The sequence is an HP" if is_hp(arr) else "Not an HP")

4. Find the AP/GP/HP of a given Array Solution in JavaScript Try on Compiler 
function isAP(arr) {
    // Compute common difference
    let d = arr[1] - arr[0];

    // Check if every term follows the AP rule
    for (let i = 2; i < arr.length; i++) {
        if (arr[i] - arr[i - 1] !== d) {
            return false;
        }
    }
    return true;
}

function isGP(arr) {
    // Compute common ratio
    let r = arr[1] / arr[0];

    // Check if every term follows the GP rule
    for (let i = 2; i < arr.length; i++) {
        if (arr[i] / arr[i - 1] !== r) {
            return false;
        }
    }
    return true;
}

function isHP(arr) {
    // Convert to reciprocal and check if it forms an AP
    let reciprocal = arr.map(x => 1 / x);
    
    return isAP(reciprocal);
}

function solve(stdin) {
    // Parse input into an array of numbers
    let arr = stdin.trim().split(" ").map(Number);

    // Check and print results
    console.log(isAP(arr) ? "The sequence is an AP" : "Not an AP");
    console.log(isGP(arr) ? "The sequence is a GP" : "Not a GP");
    console.log(isHP(arr) ? "The sequence is an HP" : "Not an HP");
}

// Accept stdin
;(() => {
    process.stdin.resume();
    process.stdin.setEncoding('utf-8');

    let input = '';
    process.stdin.on('data', (chunk) => {
        input += chunk;
    });

    process.stdin.on('end', () => {
        solve(input);
    });
})();

Find the AP/GP/HP of a given Array Solution Complexity Analysis

Time Complexity: O(n)

1. Checking for Arithmetic Progression (AP)

  • The isAP(int[] arr) function:
    • Computes the common difference O(1).
    • Iterates through the array O(n).

Time Complexity: O(n)

2. Checking for Geometric Progression (GP)

  • The isGP(int[] arr) function:
    • Computes the common ratio O(1).
    • Iterates through the array O(n).

Time Complexity: O(n)

3. Checking for Harmonic Progression (HP)

  • The isHP(int[] arr) function:
    • Computes the reciprocals of elements O(n).
    • Calls isAPDouble(double[] arr), which takes O(n).

Total Time Complexity for HP: O(n) + O(n) = O(n)

Space Complexity: O(1)

Auxiliary Space Complexity
Auxiliary Space Complexity refers to the extra space required by an algorithm other than input space.

1. Space for Arithmetic and Geometric Progression Checks

  • Both isAP(int[] arr) and isGP(int[] arr) use only a few integer variables.
  • They require O(1) auxiliary space.

2. Space for Harmonic Progression Check

  • isHP(int[] arr) creates a double[] reciprocal of size n → O(n) auxiliary space.

Total Space Complexity

1. Input Storage: The input array arr[n] requires O(n) space.

2. Auxiliary Storage
AP and GP require O(1) space.
HP requires O(n) space (due to the reciprocal array).

Final Total Space Complexity
O(n)+O(n)=O(n)

Final Thoughts

We explored: AP – Addition-based sequence
GP – Multiplication-based sequence
HP – Reciprocal of an AP