Подмассив максимальной длины с LCM, равным продукту

Опубликовано: 5 Января, 2022

Для заданного arr [] задача состоит в том, чтобы найти максимальную длину подмассива, такую, чтобы НОК подмассива была равна произведению чисел в подмассиве. Если действительный подмассив не существует, выведите -1 .

Примечание: длина подмассива должна быть ≥ 2.

Примеры:

Input: arr[] = { 6, 10, 21 }
Output: 2
The sub-array { 10, 21 } satisfies the condition.
Input: arr[] = { 2, 2, 4 }
Output: -1
No sub-array satisfies the condition. Hence the output is -1.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход: запускайте вложенные циклы, чтобы проверить условие для каждого возможного подмассива длины ≥ 2. Если подмассив удовлетворяет условию, обновите ans = max (ans, length (sub-array)) . В конце выведите ответ.

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ implementation of the above approach
 #include <bits/stdc++.h>
 using namespace std;
 #define ll long long
 // Function to calculate gcd(a, b)
 int gcd( int a, int b)
 {
    if (b == 0)
        return a;
    return gcd(b, a % b);
 }
 // Function to return max length of subarray
 // that satisfies the condition
 int maxLengthSubArray( const int * arr, int n)
 {
    int maxLen = -1;
    for ( int i = 0; i < n - 1; i++) {
        for ( int j = i + 1; j < n; j++) {
            ll lcm = 1LL * arr[i];
            ll product = 1LL * arr[i];
            // Update LCM and product of the
            // sub-array
            for ( int k = i + 1; k <= j; k++) {
                lcm = (((arr[k] * lcm)) /
                          (gcd(arr[k], lcm)));
                product = product * arr[k];
            }
            // If the current sub-array satisfies
            // the condition
            if (lcm == product) { 
                // Choose the maximum
                maxLen = max(maxLen, j - i + 1);
            }
        }
    }
    return maxLen;
 }
 // Driver code
 int main()
 {
    int arr[] = { 6, 10, 21 };
    int n = sizeof (arr) / sizeof (arr[0]);
    cout << maxLengthSubArray(arr, n);
    return 0;
 }

Джава

 // Java implementation of the above approach
 import java.util.*;
 class GFG
 {
 // Function to calculate gcd(a, b)
 static int gcd( int a, int b)
 {
    if (b == 0 )
        return a;
    return gcd(b, a % b);
 }
 // Function to return max length of subarray
 // that satisfies the condition
 static int maxLengthSubArray( int arr[], int n)
 {
    int maxLen = - 1 ;
    for ( int i = 0 ; i < n - 1 ; i++)
    {
        for ( int j = i + 1 ; j < n; j++)
        {
            int lcm = 1 * arr[i];
            int product = 1 * arr[i]; 
            // Update LCM and product of the
            // sub-array
            for ( int k = i + 1 ; k <= j; k++)
            
            {
                lcm = (((arr[k] * lcm)) /
                        (gcd(arr[k], lcm)));
                product = product * arr[k];
            }
            // If the current sub-array satisfies
            // the condition
            if (lcm == product)
            {
                // Choose the maximum
                maxLen = Math.max(maxLen, j - i + 1 );
            }
        }
    }
    return maxLen;
 }
 // Driver code
 public static void main(String args[])
 {
    int arr[] = { 6 , 10 , 21 };
    int n = arr.length;
    System.out.println(maxLengthSubArray(arr, n));
 }
 }
 // This code is contributed by
 // Shashank_Sharma

Python3

 # Python3 implementation of the
 # above approach
 # Function to calculate gcd(a, b)
 def gcd(a, b):
    if (b = = 0 ):
        return a
    return gcd(b, a % b)
 # Function to return max length of
 # subarray that satisfies the condition
 def maxLengthSubArray(arr, n): 
    maxLen = - 1
    for i in range (n - 1 ):
        for j in range (n):
            lcm = arr[i]
            product = arr[i] 
            # Update LCM and product of the
            # sub-array
            for k in range (i + 1 , j + 1 ):
                lcm = (((arr[k] * lcm)) / /
                    (gcd(arr[k], lcm)))
                product = product * arr[k]
            
            # If the current sub-array satisfies
            # the condition
            if (lcm = = product): 
                # Choose the maximum
                maxLen = max (maxLen, j - i + 1 )
    return maxLen
 # Driver code
 arr = [ 6 , 10 , 21 ]
 n = len (arr)
 print (maxLengthSubArray(arr, n))
 # This code is contributed by
 # mohit kumar 29

C #

 // C# implementation of the above approach
 using System;
 class GFG
 {
 // Function to calculate gcd(a, b)
 static int gcd( int a, int b)
 {
    if (b == 0)
        return a;
    return gcd(b, a % b);
 }
 // Function to return max length of subarray
 // that satisfies the condition
 static int maxLengthSubArray( int [] arr, int n)
 {
    int maxLen = -1;
    for ( int i = 0; i < n - 1; i++)
    {
        for ( int j = i + 1; j < n; j++)
        {
            int lcm = 1 * arr[i];
            int product = 1 * arr[i]; 
            // Update LCM and product of the
            // sub-array
            for ( int k = i + 1; k <= j; k++)
            
            {
                lcm = (((arr[k] * lcm)) /
                        (gcd(arr[k], lcm)));
                product = product * arr[k];
            }
            // If the current sub-array satisfies
            // the condition
            if (lcm == product)
            {
                // Choose the maximum
                maxLen = Math.Max(maxLen, j - i + 1);
            }
        }
    }
    return maxLen;
 }
 // Driver code
 public static void Main()
 {
    int [] arr = { 6, 10, 21 };
    int n = arr.Length;
    Console.Write(maxLengthSubArray(arr, n));
 }
 }
 // This code is contributed by ita_c

PHP

 <?php
 // PHP implementation of the above approach
 // Function to calculate gcd(a, b)
 function gcd( $a , $b )
 {
    if ( $b == 0)
        return $a ;
    return gcd( $b , $a % $b );
 }
 // Function to return max length of subarray
 // that satisfies the condition
 function maxLengthSubArray(& $arr , $n )
 {
    $maxLen = -1;
    for ( $i = 0; $i < $n - 1; $i ++)
    {
        for ( $j = $i + 1; $j < $n ; $j ++)
        {
            $lcm = $arr [ $i ];
            $product = $arr [ $i ]; 
            // Update LCM and product of the
            // sub-array
            for ( $k = $i + 1; $k <= $j ; $k ++)
            {
                $lcm = ((( $arr [ $k ] * $lcm )) /
                        (gcd( $arr [ $k ], $lcm )));
                $product = $product * $arr [ $k ];
            }
            // If the current sub-array satisfies
            // the condition
            if ( $lcm == $product )
            {
                // Choose the maximum
                $maxLen = max( $maxLen , $j - $i + 1);
            }
        }
    }
    return $maxLen ;
 }
 // Driver code
 $arr = array (6, 10, 21 );
 $n = sizeof( $arr );
 echo (maxLengthSubArray( $arr , $n ));
 // This code is contributed by Shivi_Aggarwal
 ?>

Javascript

 <script>
 // Javascript implementation of the above approach
 // Function to calculate gcd(a, b)
 function gcd(a,b)
 {
    if (b == 0)
        return a;
    return gcd(b, a % b);
 }
 // Function to return max length of subarray
 // that satisfies the condition
 function maxLengthSubArray(arr,n)
 {
    let maxLen = -1;
    for (let i = 0; i < n - 1; i++)
    {
        for (let j = i + 1; j < n; j++)
        {
            let lcm = 1 * arr[i];
            let product = 1 * arr[i];
 
            // Update LCM and product of the
            // sub-array
            for (let k = i + 1; k <= j; k++)
             
            {
                lcm = (((arr[k] * lcm)) /
                        (gcd(arr[k], lcm)));
                product = product * arr[k];
            }
 
            // If the current sub-array satisfies
            // the condition
            if (lcm == product)
            {
 
                // Choose the maximum
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }
    return maxLen;
 }
 // Driver code
 let arr=[6, 10, 21 ];
 let n = arr.length;
 document.write(maxLengthSubArray(arr, n));
    
// This code is contributed by unknown2108
 </script>

Выход:

Эффективный подход: НОК подмассива будет равняться его произведению, если никакие два элемента в подмассиве не имеют общего множителя.

Например:

arr[] = { 6, 10, 21 }
Prime factorization yields:
arr[] = { 2 * 3, 2 * 5, 3 * 7 }
[6, 10] has 2 as a common factor.
[6, 10, 21] has 2 as a common factor between 6 and 10.
Sub-array [10, 21] has no common factor between any 2 elements. Therefore, answer = 2.

Во-первых, разложение чисел на простые множители выполняется для работы с множителями. Чтобы вычислить подмассив, в котором нет двух элементов, имеющих общий фактор, мы используем метод двух указателей.

Два указателя запускаются справа, и они представляют текущий подмассив. Добавляем элементы в подмассив справа. Теперь есть два сценария:

Элемент добавляется в текущий подмассив, если он не имеет общего фактора с текущими элементами в подмассиве. Если общий множитель найден, то, начиная слева, элементы впоследствии удаляются до тех пор, пока не будет найден общий множитель с вновь добавленным элементом.
Если между вновь добавленным элементом и существующими элементами нет общих факторов, обновите ans = max (ans, длина подмассива)

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ implementation of the above approach
 #include <bits/stdc++.h>
 #define pb push_back
 #define N 100005
 #define MAX 1000002
 #define mem(a, b) memset(a, b, sizeof(a))
 using namespace std;
 int prime[MAX];
 // Stores array of primes for every element
 vector< int > v[N];
 // Stores the position of a prime in the subarray
 // in two pointer technique
 int f[MAX];
 // Function to store smallest prime factor of numbers
 void sieve()
 {
    prime[0] = prime[1] = 1;
    for ( int i = 2; i < MAX; i++) {
        if (!prime[i]) {
            for ( int j = i * 2; j < MAX; j += i) {
                if (!prime[j])
                    prime[j] = i;
            }
        }
    }
    for ( int i = 2; i < MAX; i++) { 
        // If number is prime,
        // then smallest prime factor is the
        // number itself
        if (!prime[i])
            prime[i] = i;
    }
 }
 // Function to return maximum length of subarray
 // with LCM = product
 int maxLengthSubArray( int * arr, int n)
 {
    // Initialize f with -1
    mem(f, -1);
    for ( int i = 0; i < n; ++i) { 
        // Prime factorization of numbers
        // Store primes in a vector for every element
        while (arr[i] > 1) {
            int p = prime[arr[i]];
            arr[i] /= p;
            v[i].pb(p);
        }
    }
    // Two pointers l and r
    // denoting left and right of subarray
    int l = 0, r = 1, ans = -1; 
    // f is a mapping.
    // prime -> index in the current subarray
    // With the help of f,
    // we can detect whether a prime has
    // already occurred in the subarray
    for ( int i : v[0]) {
        f[i] = 0;
    }
    while (l <= r && r < n) {
        int flag = 0; 
        for ( int i = 0; i < v[r].size(); i++) { 
            // Map the prime to the index
            if (f[v[r][i]] == -1 || f[v[r][i]] == r) {
                f[v[r][i]] = r;
            }
            // If already occurred then,
            // start removing elements from the left
            else {
                flag = 1;
                break ;
            }
        }
        // Remove elements if flag = 1
        if (flag) { 
            // Nullify entries of element at index 'l'
            for ( int i : v[l]) {
                f[i] = -1;
            }
            // Increment 'l'
            l++;
        }
        else { 
            // Maximize the answer when
            // no common factor is found
            ans = max(ans, r - l + 1);
            r++;
        }
    }
    // One length subarray is discarded
    if (ans == 1)
        ans = -1;
    return ans;
 }
 // Driver code
 int main()
 {
    sieve();
    int arr[] = { 6, 10, 21 };
    int n = sizeof (a
            

                    
                                            Technical Scripter
                                            Алгоритмы
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИКоличество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023


    


        
            
                
                    
                        
                        < PROGLER >
                    
                
                
                    
                        Общее
                        
                        Контакты
                        Политика конфиденциальности
                    
                    
                        Обучение
                        Блог
                    
                
            
            
                © progler.ru 2024. Все права защищены.