기하학적 진행을 형성하는 정렬된 배열에서 모든 삼중항을 찾습니다.
고유한 양의 정수로 정렬된 배열이 주어지면 적분 공비로 기하학적 진행을 형성하는 모든 삼중항을 인쇄합니다.
기하수열은 첫 번째 항 이후의 각 항이 이전 항에 공비라고 불리는 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 using namespace std ; // The function prints three elements in GP if exists // Assumption: arr[0..n-1] is sorted. 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 ( arr [ j ] % arr [ i ] == 0 && arr [ k ] % arr [ j ] == 0 && arr [ j ] / arr [ i ] == arr [ k ] / arr [ j ]) { // print the triplet cout < < arr [ i ] < < ' ' < < arr [ j ] < < ' ' < < arr [ k ] < < endl ; // 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 ( arr [ j ] % arr [ i ] == 0 && arr [ k ] % arr [ j ] == 0 ) { if ( 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 ( arr [ j ] % arr [ i ] == 0 ) k ++ ; else i -- ; } } } // Driver code int 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 = sizeof ( arr ) / sizeof ( arr [ 0 ]); findGeometricTriplets ( arr n ); return 0 ; }
Java // 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 # 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# // 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.
JavaScript < 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 ( arr n ) { // 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(n 2 ) 모든 j에 대해 선형 시간에서 i와 k를 찾습니다.
보조 공간: O(1) 추가 공간을 사용하지 않았기 때문입니다.
