別個の正の整数のソートされた配列を指定すると、整数公比で幾何級数を形成するすべての 3 つ組が出力されます。
等比数列は一連の数値であり、最初の項以降の各項は、前の項に公比と呼ばれるゼロ以外の固定数を乗算することによって求められます。たとえば、数列 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
このアイデアは、2 番目の要素から開始してすべての要素を中間要素として固定し、トリプレット内の他の 2 つの要素 (1 つは小さく、もう 1 つは大きい) を検索することです。要素 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) 余分なスペースを使用していないためです。