Written in C++, find the number of quadruples whose first three terms are arithmetic sequences and the last three terms are geometric sequences.

In this article we will describe all the possible ways to find quaternions using A.P. for the first 3 terms and G.P. for the last 3 terms. First, we will explain the basic definitions of arithmetic progression (A.P.) and geometric progression (G.P.).

Arithmetic Progression (A.P.) - It is a sequence of numbers in which the common deviation (d) is the same or constant, meaning that the difference between two consecutive numbers is constant. For example: 1,3,5,7,9 | d = 2

Geometric Progression (G.P.) - This is a sequence of numbers where the common ratios (r) are the same, which means So we can multiply the previous number with the fixed number. For example: 3, 6, 12, 24, .... | r = 2

In this problem, we need to determine how many index quadruples (a , b, c, d). As a result, arr[a], arr[b], and arr[c] are in A.P., while arr[d], arr[c], and arr[b] are in G.P. All four-tuples in it should be deterministic. Here is the example -

Input : arr[ ] = { 9, 6, 4, 2, 1, 2 }
Output : 2
Explanation: Elements in the quadruples are at { 3, 2, 1, 0 } and { 5, 2, 1, 0 } indexes where quadruples are { 2, 4, 6, 9 } for both positions.

Input : arr[ ] = { 2, 6, 1, 4, 2 }
Output : 2
Explanation: Elements in the quadruples are at { 1, 3, 0, 2 } and { 1, 3, 4, 2 } indexes where quadruples are { 6, 4, 2, 1 } for both positions.

Methods of finding solutions

Now, we will describe two different methods of finding solutions-

brute force methods

Here is a simple way to solve this problem using four nested loops and then check if the first three elements are in A.P. If yes, then check if the last 3 elements are in G.P. If so, add 1 to the count variable. However, this method is very time-consuming as its time complexity is O(n4).

Efficient method

Example

#include <bits/stdc++.h>
using namespace std;
int main (){
    unordered_map < int, int >map;
    int arr[] = { 2, 6, 1, 4, 2 };
    int size = sizeof (arr) / sizeof (arr[0]);
    // Processing every elent and increasing the count
    for (int a = 0; a < size; a++)
      map[arr[a]]++;

    int count = 0;
    // Running two nested loops for second & third element
    for (int b = 0; b < size; b++){
        for (int c = 0; c < size; c++){
            if (b == c)
                continue;
                // Decreasing the count
                map[arr[b]]--;
            map[arr[c]]--;
            // Finding the first element using common difference
            int first = arr[b] - (arr[c] - arr[b]);
            // Finding the fourth element using GP
            int fourth = (arr[c] * arr[c]) / arr[b];
            if ((arr[c] * arr[c]) % arr[b] == 0){
                // Increment count if not equal
                if (arr[b] != arr[c])
                    count += map[first] * map[fourth];
                else
                 count += map[first] * (map[fourth] - 1);
            }
            map[arr[b]]++;
            map[arr[c]]++;
        }
    }
    cout <<"Number of quadruples: " << count;
    return 0;
}

Output

Number of quadruples: 2

Explanation of the above code

In this code, we use combinatorics to do the second and third elements using two nested loops and find the first element using arr[a] – (arr[c] – arr[b]) and the fourth element arr[c] * arr[c] / arr[b]. So, by keeping the second and third elements fixed, the number of quaternions indexed by A and B is the count of the first number * the fourth number. The time complexity of the above code is O(n2).

Conclusion

In this article, we solved the problem of finding quaternions, where the first three terms are in AP and the last three terms are in GP. We discussed using Bruteforce[ O( n4) ] and Efficient method [ O(n2) ] are two ways to solve this problem.

We used C to solve this problem, which can also be solved in various other languages, such as java, python , C or any other programming language.

The above is the detailed content of Written in C++, find the number of quadruples whose first three terms are arithmetic sequences and the last three terms are geometric sequences.. For more information, please follow other related articles on the PHP Chinese website!