고유한 양의 정수로 정렬된 배열이 주어지면 적분 공비로 기하학적 진행을 형성하는 모든 삼중항을 인쇄합니다.
기하수열은 첫 번째 항 이후의 각 항이 이전 항에 공비라고 불리는 0이 아닌 고정된 수를 곱하여 구하는 수열입니다. 예를 들어 수열 2 6 18 54...는 공비가 3인 등비수열입니다.
예:
Input: arr = [1 2 6 10 18 54] Output: 2 6 18 6 18 54 Input: arr = [2 8 10 15 16 30 32 64] Output: 2 8 32 8 16 32 16 32 64 Input: arr = [ 1 2 6 18 36 54] Output: 2 6 18 1 6 36 6 18 54
아이디어는 두 번째 요소부터 시작하여 모든 요소를 중간 요소로 고정하고 세 개의 요소(하나는 더 작고 하나는 더 큰)에서 다른 두 요소를 검색하는 것입니다. arr[j] 요소가 기하학적 수열의 중간에 있으려면 다음과 같은 요소 arr[i] 및 arr[k]가 존재해야 합니다.
arr[j] / arr[i] = r and arr[k] / arr[j] = r where r is an positive integer and 0 <= i < j and j < k <= n - 1
아래는 위의 아이디어를 구현한 것입니다.
C++// C++ program to find if there exist three elements in // Geometric Progression or not #include
// Java program to find if there exist three elements in // Geometric Progression or not import java.util.*; class GFG { // The function prints three elements in GP if exists // Assumption: arr[0..n-1] is sorted. static void findGeometricTriplets(int arr[] int n) { // One by fix every element as middle element for (int j = 1; j < n - 1; j++) { // Initialize i and k for the current j int i = j - 1 k = j + 1; // Find all i and k such that (i j k) // forms a triplet of GP while (i >= 0 && k <= n - 1) { // if arr[j]/arr[i] = r and arr[k]/arr[j] = r // and r is an integer (i j k) forms Geometric // Progression while (i >= 0 && arr[j] % arr[i] == 0 && arr[k] % arr[j] == 0 && arr[j] / arr[i] == arr[k] / arr[j]) { // print the triplet System.out.println(arr[i] +' ' + arr[j] + ' ' + arr[k]); // Since the array is sorted and elements // are distinct. k++ ; i--; } // if arr[j] is multiple of arr[i] and arr[k] is // multiple of arr[j] then arr[j] / arr[i] != // arr[k] / arr[j]. We compare their values to // move to next k or previous i. if(i >= 0 && arr[j] % arr[i] == 0 && arr[k] % arr[j] == 0) { if(i >= 0 && arr[j] / arr[i] < arr[k] / arr[j]) i--; else k++; } // else if arr[j] is multiple of arr[i] then // try next k. Else try previous i. else if (i >= 0 && arr[j] % arr[i] == 0) k++; else i--; } } } // Driver code public static void main(String[] args) { // int arr[] = {1 2 6 10 18 54}; // int arr[] = {2 8 10 15 16 30 32 64}; // int arr[] = {1 2 6 18 36 54}; int arr[] = {1 2 4 16}; // int arr[] = {1 2 3 6 18 22}; int n = arr.length; findGeometricTriplets(arr n); } } // This code is contributed by Rajput-Ji
# Python 3 program to find if # there exist three elements in # Geometric Progression or not # The function prints three elements # in GP if exists. # Assumption: arr[0..n-1] is sorted. def findGeometricTriplets(arr n): # One by fix every element # as middle element for j in range(1 n - 1): # Initialize i and k for # the current j i = j - 1 k = j + 1 # Find all i and k such that # (i j k) forms a triplet of GP while (i >= 0 and k <= n - 1): # if arr[j]/arr[i] = r and # arr[k]/arr[j] = r and r # is an integer (i j k) forms # Geometric Progression while (arr[j] % arr[i] == 0 and arr[k] % arr[j] == 0 and arr[j] // arr[i] == arr[k] // arr[j]): # print the triplet print( arr[i] ' ' arr[j] ' ' arr[k]) # Since the array is sorted and # elements are distinct. k += 1 i -= 1 # if arr[j] is multiple of arr[i] # and arr[k] is multiple of arr[j] # then arr[j] / arr[i] != arr[k] / arr[j]. # We compare their values to # move to next k or previous i. if(arr[j] % arr[i] == 0 and arr[k] % arr[j] == 0): if(arr[j] // arr[i] < arr[k] // arr[j]): i -= 1 else: k += 1 # else if arr[j] is multiple of # arr[i] then try next k. Else # try previous i. elif (arr[j] % arr[i] == 0): k += 1 else: i -= 1 # Driver code if __name__ =='__main__': arr = [1 2 4 16] n = len(arr) findGeometricTriplets(arr n) # This code is contributed # by ChitraNayal
// C# program to find if there exist three elements // in Geometric Progression or not using System; class GFG { // The function prints three elements in GP if exists // Assumption: arr[0..n-1] is sorted. static void findGeometricTriplets(int []arr int n) { // One by fix every element as middle element for (int j = 1; j < n - 1; j++) { // Initialize i and k for the current j int i = j - 1 k = j + 1; // Find all i and k such that (i j k) // forms a triplet of GP while (i >= 0 && k <= n - 1) { // if arr[j]/arr[i] = r and arr[k]/arr[j] = r // and r is an integer (i j k) forms Geometric // Progression while (i >= 0 && arr[j] % arr[i] == 0 && arr[k] % arr[j] == 0 && arr[j] / arr[i] == arr[k] / arr[j]) { // print the triplet Console.WriteLine(arr[i] +' ' + arr[j] + ' ' + arr[k]); // Since the array is sorted and elements // are distinct. k++ ; i--; } // if arr[j] is multiple of arr[i] and arr[k] is // multiple of arr[j] then arr[j] / arr[i] != // arr[k] / arr[j]. We compare their values to // move to next k or previous i. if(i >= 0 && arr[j] % arr[i] == 0 && arr[k] % arr[j] == 0) { if(i >= 0 && arr[j] / arr[i] < arr[k] / arr[j]) i--; else k++; } // else if arr[j] is multiple of arr[i] then // try next k. Else try previous i. else if (i >= 0 && arr[j] % arr[i] == 0) k++; else i--; } } } // Driver code static public void Main () { // int arr[] = {1 2 6 10 18 54}; // int arr[] = {2 8 10 15 16 30 32 64}; // int arr[] = {1 2 6 18 36 54}; int []arr = {1 2 4 16}; // int arr[] = {1 2 3 6 18 22}; int n = arr.Length; findGeometricTriplets(arr n); } } // This code is contributed by ajit.
<script> // Javascript program to find if there exist three elements in // Geometric Progression or not // The function prints three elements in GP if exists // Assumption: arr[0..n-1] is sorted. function findGeometricTriplets(arrn) { // One by fix every element as middle element for (let j = 1; j < n - 1; j++) { // Initialize i and k for the current j let i = j - 1 k = j + 1; // Find all i and k such that (i j k) // forms a triplet of GP while (i >= 0 && k <= n - 1) { // if arr[j]/arr[i] = r and arr[k]/arr[j] = r // and r is an integer (i j k) forms Geometric // Progression while (i >= 0 && arr[j] % arr[i] == 0 && arr[k] % arr[j] == 0 && arr[j] / arr[i] == arr[k] / arr[j]) { // print the triplet document.write(arr[i] +' ' + arr[j] + ' ' + arr[k]+'
'); // Since the array is sorted and elements // are distinct. k++ ; i--; } // if arr[j] is multiple of arr[i] and arr[k] is // multiple of arr[j] then arr[j] / arr[i] != // arr[k] / arr[j]. We compare their values to // move to next k or previous i. if(i >= 0 && arr[j] % arr[i] == 0 && arr[k] % arr[j] == 0) { if(i >= 0 && arr[j] / arr[i] < arr[k] / arr[j]) i--; else k++; } // else if arr[j] is multiple of arr[i] then // try next k. Else try previous i. else if (i >= 0 && arr[j] % arr[i] == 0) k++; else i--; } } } // Driver code // int arr[] = {1 2 6 10 18 54}; // int arr[] = {2 8 10 15 16 30 32 64}; // int arr[] = {1 2 6 18 36 54}; let arr = [1 2 4 16]; // int arr[] = {1 2 3 6 18 22}; let n = arr.length; findGeometricTriplets(arr n); // This code is contributed by avanitrachhadiya2155 </script>
산출
1 2 4 1 4 16
시간 복잡도 위의 해는 O(n2) 모든 j에 대해 선형 시간에서 i와 k를 찾습니다.
보조 공간: O(1) 추가 공간을 사용하지 않았기 때문입니다.