Given N and K, the task is to print N lines where each line contains 4 numbers such that every among those 4 numbers has a GCD K and the maximum number used in N*4 should be minimized.
Note: In case of multiple outputs, print any one.
Examples:
Input: N = 1, K = 1
Output: 1 2 3 5
Every pair among 1, 2, 3 and 5 gives a GCD K and the largest number among these is 5 which the minimum possible.Input: 2 2
Output:
2 4 6 22
14 18 10 16
In the above input, the maximum number is 22, which is the minimum possible to make 2 lines of 4 numbers.
Approach: The first observation is that if we can solve the given problem for K=1, we can solve the problem with GCD K by simply multiplying the answers with K. We know that any three consecutive odd numbers have a GCD 1 always when paired, so three numbers of every line can be easily obtained. Hence the lines will look like:
1 3 5 _ 7 9 11 _ 13 15 17 _ . . .
An even number cannot be inserted always, because inserting 6 in third line will give GCD(6, 9) as 3. So the best number that can be inserted is a number between the first two off numbers of every line. Hence the pattern looks like:
1 2 3 5 7 8 9 11 13 14 15 17 . . .
To obtain given GCD K, one can easily multiply K to the obtained numbers. Hence for i-th line:
- the first number will be k * (6*i+1)
- the second number will be k * (6*i+1)
- the third number will be k * (6*i+3)
- the fourth number will be k * (6*i+5)
The maximum number among N*4 numbers will be k * (6*i – 1)
Below is the implementation of the above approach.
C++
// C++ implementation of the// above approach#include <bits/stdc++.h>using namespace std;// Function to print N linesvoid printLines(int n, int k){ // Iterate N times to print N lines for (int i = 0; i < n; i++) { cout << k * (6 * i + 1) << " " << k * (6 * i + 2) << " " << k * (6 * i + 3) << " " << k * (6 * i + 5) << endl; }}// Driver Codeint main(){ int n = 2, k = 2; printLines(n, k); return 0;} |
Java
// Java implementation of the// above approachimport java.util.*;import java.lang.*;import java.io.*;class GFG{// Function to print N linesstatic void printLines(int n, int k){ // Iterate N times to print N lines for (int i = 0; i < n; i++) { System.out.println ( k * (6 * i + 1) + " " + k * (6 * i + 2) + " " + k * (6 * i + 3) + " " + k * (6 * i + 5) ); }}// Driver Codepublic static void main(String args[]){ int n = 2, k = 2; printLines(n, k);}} |
Python3
# Python implementation of the# above approach. # Function to print N lines def printLines(n, k) : # Iterate N times to print N lines for i in range(n) : print( k * (6 * i + 1), k * (6 * i + 2), k * (6 * i + 3), k * (6 * i + 5)) # Driver code if __name__ == "__main__" : n, k = 2, 2 printLines(n, k)# This code is contributed by ANKITRAI1 |
PHP
<?php// Function to print N linesfunction printLines($n, $k){ // Iterate N times to print N lines for ($i = 0; $i < $n; $i++) { echo ($k * (6 * $i + 1)); echo (" "); echo ($k * (6 * $i + 2)); echo (" "); echo ($k * (6 * $i + 3)); echo (" "); echo ($k * (6 * $i + 5)); echo ("\n"); }}// Driver Code$n = 2;$k = 2;printLines($n, $k); // This code is contributed // by Shivi_Aggarwal?> |
C#
// C# implementation of the// above approachusing System;class GFG{// Function to print N linesstatic void printLines(int n, int k){ // Iterate N times to print N lines for (int i = 0; i < n; i++) { Console.WriteLine ( k * (6 * i + 1) + " " + k * (6 * i + 2) + " " + k * (6 * i + 3) + " " + k * (6 * i + 5) ); }}// Driver Codepublic static void Main(){ int n = 2, k = 2; printLines(n, k);}}// This code is contributed// by Akanksha Rai(Abby_akku) |
Javascript
<script>// javascript implementation of the// above approach // Function to print N lines function printLines(n , k) { // Iterate N times to print N lines for (i = 0; i < n; i++) { document.write(k * (6 * i + 1) + " " + k * (6 * i + 2) + " " + k * (6 * i + 3) + " " + k * (6 * i + 5)+"<br/>"); } } // Driver Code var n = 2, k = 2; printLines(n, k);// This code is contributed by umadevi9616 </script> |
2 4 6 10 14 16 18 22
Time Complexity: O(N*4), as we are using a loop to traverse N times and doing 4 operations in each traversal.
Auxiliary Space: O(1), as we are not using any extra space.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
