Generate an array with product of all subarrays of length exceeding one divisible by K
Given two positive integers N and K, the task is to generate an array of length N such that the product of every subarray of length greater than 1 must be divisible by K and the maximum element of the array must be less than K. If no such array is possible, then print -1.
Examples:
Input: N = 3, K = 20
Output: {15, 12, 5}
Explanation: All subarrays of length greater than 1 are {15, 12}, {12, 5}, {15, 12, 5} and their corresponding products are 180, 60 and 900, which are all divisible by 20.Input: N = 4, K = 100
Output: {90, 90, 90, 90}
Approach: The given problem can be solved by the following observations:
It can be observed that by making the product of every subarray of length 2 divisible by K, the product of every subarray of length greater than 2 will automatically be divisible by K.
Therefore, the idea is to take two divisors of K, say d1 and d2, such that d1 * d2 = K and place them alternatively in the array. Follow the steps below to solve the problem:
- Initialize two integer variables d1 and d2.
- Check if K is prime. If found to be true, print -1.
- Otherwise, calculate the divisors of K and store two divisors in d1 and d2.
- After that, traverse from i = 0 to N – 1.
- Print d1 if i is even. Otherwise, print d2.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to check if the required // array can be generated or not void array_divisbleby_k( int N, int K) { // To check if divisor exists bool flag = false ; // To store divisors of K int d1, d2; // Check if K is prime or not for ( int i = 2; i * i <= K; i++) { if (K % i == 0) { flag = true ; d1 = i; d2 = K / i; break ; } } // If array can be generated if (flag) { // Print d1 and d2 alternatively for ( int i = 0; i < N; i++) { if (i % 2 == 1) { cout << d2 << " " ; } else { cout << d1 << " " ; } } } else { // No such array can be generated cout << -1; } } // Driver Code int main() { // Given N and K int N = 5, K = 21; // Function Call array_divisbleby_k(N, K); return 0; } |
Java
// Java program for the above approach class GFG{ // Function to check if the required // array can be generated or not public static void array_divisbleby_k( int N, int K) { // To check if divisor exists boolean flag = false ; // To store divisors of K int d1 = 0 , d2 = 0 ; // Check if K is prime or not for ( int i = 2 ; i * i <= K; i++) { if (K % i == 0 ) { flag = true ; d1 = i; d2 = K / i; break ; } } // If array can be generated if (flag) { // Print d1 and d2 alternatively for ( int i = 0 ; i < N; i++) { if (i % 2 == 1 ) { System.out.print(d2 + " " ); } else { System.out.print(d1 + " " ); } } } else { // No such array can be generated System.out.print(- 1 ); } } // Driver Code public static void main(String[] args) { // Given N and K int N = 5 , K = 21 ; // Function Call array_divisbleby_k(N, K); } } // This code is contributed by divyesh072019 |
Python3
# Python3 program for the above approach # Function to check if the required # array can be generated or not def array_divisbleby_k(N, K): # To check if divisor exists flag = False # To store divisors of K d1, d2 = 0 , 0 # Check if K is prime or not for i in range ( 2 , int (K * * ( 1 / 2 )) + 1 ): if (K % i = = 0 ): flag = True d1 = i d2 = K / / i break # If array can be generated if (flag): # Print d1 and d2 alternatively for i in range (N): if (i % 2 = = 1 ): print (d2, end = " " ) else : print (d1, end = " " ) else : # No such array can be generated print ( - 1 ) # Driver Code if __name__ = = "__main__" : # Given N and K N = 5 K = 21 # Function Call array_divisbleby_k(N, K) # This code is contributed by AnkThon |
C#
// C# program for the above approach using System; class GFG{ // Function to check if the required // array can be generated or not public static void array_divisbleby_k( int N, int K) { // To check if divisor exists bool flag = false ; // To store divisors of K int d1 = 0, d2 = 0; // Check if K is prime or not for ( int i = 2; i * i <= K; i++) { if (K % i == 0) { flag = true ; d1 = i; d2 = K / i; break ; } } // If array can be generated if (flag) { // Print d1 and d2 alternatively for ( int i = 0; i < N; i++) { if (i % 2 == 1) { Console.Write(d2 + " " ); } else { Console.Write(d1 + " " ); } } } else { // No such array can be generated Console.Write(-1); } } // Driver Code public static void Main( string [] args) { // Given N and K int N = 5, K = 21; // Function Call array_divisbleby_k(N, K); } } // This code is contributed by AnkThon |
Javascript
<script> // Javascript program for the above approach // Function to check if the required // array can be generated or not function array_divisbleby_k(N, K) { // To check if divisor exists let flag = false ; // To store divisors of K let d1 = 0, d2 = 0; // Check if K is prime or not for (let i = 2; i * i <= K; i++) { if (K % i == 0) { flag = true ; d1 = i; d2 = K / i; break ; } } // If array can be generated if (flag) { // Print d1 and d2 alternatively for (let i = 0; i < N; i++) { if (i % 2 == 1) { document.write(d2 + " " ); } else { document.write(d1 + " " ); } } } else { // No such array can be generated document.write(-1); } } // Given N and K let N = 5, K = 21; // Function Call array_divisbleby_k(N, K); // This code is contributed by suresh07. </script> |
Output:
3 7 3 7 3
Time complexity: O(N + ?K)
Auxiliary space: O(1)