이 기사에서는 처음 3개 항이 A.P.에 있고 마지막 3개 항이 G.P.에 있는 사중항의 수를 찾는 모든 가능한 접근 방식을 설명합니다. 먼저 산술진행(A.P.)과 기하진행(G.P.)의 기본 정의를 설명하겠습니다.
산술 진행(A.P.) - 공차(d)가 같거나 일정한 수열로 연속되는 두 수의 차가 일정함을 의미합니다. 예:1,3,5,7,9 | d =2
기하학적 진행(G.P.) − 공비(r)가 동일한 수열로 앞의 수에 고정수를 곱하여 각 항을 찾을 수 있음을 의미합니다. 예:3, 6, 12, 24,... | r =2
이 문제에서 우리는 N 정수의 배열 arr[ ]에서 인덱스 쿼드러플(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. 해결책을 찾기 위한 접근 방식
이제 솔루션을 찾기 위한 두 가지 다른 접근 방식을 설명하겠습니다.
무차별 대입 접근
네 개의 중첩 루프를 사용하여 이 문제를 해결하는 간단한 방법입니다. 그런 다음 처음 세 개의 요소가 A.P에 있는지 확인하고, 그렇다면 마지막 세 개의 요소가 G.P에 있는지 확인합니다. 그렇다면 count 변수를 1만큼 증가시킵니다. 그러나 이 접근 방식은 시간 복잡도가 O(n4)이므로 시간이 많이 걸립니다. .
효율적인 접근
이 접근 방식에서는 먼저 모든 배열 요소의 개수를 찾은 다음 두 요소를 두 번째 및 세 번째 숫자로 간주하고 두 개의 중첩 루프를 실행하면 첫 번째 요소는 arr[b] – (arr[c] – arr[b]) 네 번째 요소는 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
위 코드 설명
이 코드에서는 조합을 사용하고 두 번째 및 세 번째 요소에 대해 두 개의 중첩 루프를 사용하고 arr[a] – (arr[c] – arr[b])로 첫 번째 요소를 찾습니다. arr[c] * arr[c] / arr[b]가 있는 네 번째 요소 . 따라서 A 및 B 인덱스의 4배 수는 두 번째 및 세 번째 요소를 고정된 상태로 유지하여 첫 번째 숫자 * 네 번째 숫자의 개수입니다. 여기서 시간 복잡도 위 코드의 O(n2) .
결론
이 글에서는 처음 3개의 항이 AP에 있고 마지막 3개의 항이 GP에 있는 쿼드러플의 수를 찾는 문제를 해결하고 Bruteforce[ O(n4) ]와 Efficient를 사용하여 이를 해결하는 두 가지 접근 방식에 대해 논의했습니다. 접근 [ O(n2) ].
우리는 C++를 사용하여 이 문제를 해결했으며 Java, python, C 또는 기타 프로그래밍 언어와 같은 다양한 다른 언어에서 이 문제를 해결할 수 있습니다.