C ++を使用して、最初の3つの用語がAPにあり、最後の3つの用語がGPにある4倍の数を見つけます。

この記事では、最初の3つの用語がA.P.にあり、最後の3つの用語がG.P.にある4倍の数を見つけるためのすべての可能なアプローチについて説明します。まず、等差数列（A.P.）と等比数列（G.P.）の基本的な定義について説明します。

等差数列（A.P。） −これは、共通の差（d）が同じまたは一定である数列であり、2つの連続する数の差が一定であることを意味します。例：1,3,5,7,9 | d =2

等比数列（G.P。） −これは、共通の比率（r）が同じ数列であり、前の数に固定数を掛けることで各項を見つけることができることを意味します。例：3、6、12、24、.... | r =2

この問題では、N個の整数の配列arr []から、インデックスの4倍（a、b、c、d）がいくつあるかを判別する必要があります。その結果、arr [a]、arr [b]、およびarr [c]はA.P.にあり、arr [d]、arr [c]、およびarr[b]はG.P.にあります。ここで、すべての4倍が明確である必要があります。これが例です-

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.

解決策を見つけるためのアプローチ

ここで、解決策を見つけるための2つの異なるアプローチについて説明します-

ブルートフォースアプローチ

4つのネストされたループを使用してこの問題を解決し、最初の3つの要素がA.Pにあるかどうかを確認するのは簡単な方法です。ある場合は、最後の3つの要素がG.Pにあるかどうかを確認します。はいの場合は、カウント変数を1ずつ増やします。ただし、このアプローチは、時間計算量がO（n4）であるため、時間がかかります。 。

効率的なアプローチ

このアプローチでは、最初にすべての配列要素の数を見つけ、次に両方の要素を2番目と3番目の数と見なし、2つのネストされたループを実行すると、最初の要素は arr [b] –（arr [c] –になります。 arr [b]） 4番目の要素はarr[c] * arr [c] / arr [b]になります 。

例

#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;
}

出力

Number of quadruples: 2

上記のコードの説明

このコードでは、組み合わせ論を使用し、2番目と3番目の要素に2つのネストされたループを使用し、 arr [a] –（arr [c] – arr [b]）で最初の要素を検索しています。 arr [c] * arr [c] / arr [b]の4番目の要素 。したがって、AおよびBインデックスによる4倍の数は、2番目と3番目の要素を固定したままにして、最初の数*4番目の数の数になります。ここで時間計算量 上記のコードのO（n2） 。

結論

この記事では、最初の3つの項がAPにあり、最後の3つの項がGPにある、4倍の数を見つける問題を解決し、Bruteforce [O（n4）]とEfficientを使用してこれを解決する2つのアプローチについて説明しました。アプローチ[O（n2）]。

この問題はC++を使用して解決しました。これにより、Java、Python、C、またはその他のプログラミング言語など、他のさまざまな言語でこの問題を解決できます。