ในบทความนี้ เราจะอธิบายทุกวิธีที่เป็นไปได้ในการค้นหาจำนวนสี่เท่าโดยที่ 3 คำแรกอยู่ใน A.P. และ 3 คำสุดท้ายอยู่ใน G.P. อันดับแรก เราจะอธิบายคำจำกัดความพื้นฐานของความก้าวหน้าทางคณิตศาสตร์ (A.P.) และความก้าวหน้าทางเรขาคณิต (G.P.)
ความก้าวหน้าทางคณิตศาสตร์ (A.P.) − เป็นลำดับของตัวเลขโดยที่ผลต่างร่วม (d) มีค่าเท่ากันหรือคงที่ ซึ่งหมายความว่าผลต่างของตัวเลขสองตัวติดต่อกันเป็นค่าคงที่ ตัวอย่างเช่น:1,3,5,7,9 | d =2
ความก้าวหน้าทางเรขาคณิต (GP) − เป็นลำดับของตัวเลขที่มีอัตราส่วนร่วม (r) เท่ากัน ซึ่งหมายความว่าเราสามารถหาแต่ละพจน์ได้โดยการคูณตัวเลขก่อนหน้าด้วยจำนวนคงที่ ตัวอย่างเช่น 3, 6, 12, 24,.... | r =2
ในปัญหานี้ เราจำเป็นต้องกำหนดจำนวนดัชนีสี่เท่า (a, b, c, d) จากอาร์เรย์ arr[ ] ของจำนวนเต็ม N เป็นผลให้ arr[a], arr[b] และ arr[c] อยู่ใน A.P. และ arr[d], arr[c] และ arr[b] อยู่ใน G.P. โดยที่สี่เท่าทั้งหมดควรจะแน่นอน นี่คือตัวอย่าง −
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 หรือไม่ ถ้าใช่ ให้ตรวจสอบว่าองค์ประกอบ 3 รายการสุดท้ายอยู่ใน G.P หรือไม่ ถ้าใช่ ให้เพิ่มตัวแปรการนับขึ้น 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
คำอธิบายของโค้ดด้านบน
ในโค้ดนี้ เราใช้ Combinatorics และใช้ลูปซ้อนสองลูปสำหรับองค์ประกอบที่สองและสาม และค้นหาองค์ประกอบแรกด้วย arr[a] – (arr[c] – arr[b]) และองค์ประกอบที่สี่ด้วย arr[c] * arr[c] / arr[b] . ดังนั้นจำนวนของสี่เท่าโดยดัชนี A และ B คือการนับของตัวเลขแรก * ตัวเลขที่สี่ โดยคงองค์ประกอบที่สองและสามคงที่ ความซับซ้อนของเวลา ของโค้ดด้านบนคือ O(n2) .
บทสรุป
ในบทความนี้ เราแก้ปัญหาการหา Number of quadruples โดยที่คำศัพท์สามคำแรกอยู่ใน AP และสามเทอมสุดท้ายอยู่ใน GP และเราพูดถึงสองแนวทางในการแก้ปัญหานี้โดยใช้ Bruteforce[ O(n4) ] และ Efficient เข้าใกล้ [ O(n2) ].
เราแก้ไขปัญหานี้โดยใช้ C++ และสามารถแก้ปัญหานี้ในภาษาอื่นๆ เช่น java, python, C หรือภาษาการเขียนโปรแกรมอื่นๆ
