Print N lines of 4 numbers such that every pair among 4 numbers has a GCD K

0 0 4 minutes read

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:

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 lines
void 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 Code
int main()
{
    int n = 2, k = 2;
    printLines(n, k);
    return 0;
}

Java

// Java implementation of the
// above approach
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG
{
// Function to print N lines
static 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 Code
public 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 lines
function 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 approach
using System;
 
class GFG
{
// Function to print N lines
static 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 Code
public 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>

Output:

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.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!