Given two integers n and g, the task is to generate an increasing sequence of n integers such that:
- The gcd of all the elements of the sequence is g.
- And, the sum of all the elements is the minimum among all possible sequences.
Examples:
Input: n = 6, g = 5
Output: 5 10 15 20 25 30Input: n = 5, g = 3
Output: 3 6 9 12 15
Approach: The sum of the sequence will be minimum when the sequence will consist of the elements:
g, 2 * g, 3 * g, 4 * g, ….., n * g.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to print the required sequence void generateSequence( int n, int g) { for ( int i = 1; i <= n; i++) cout << i * g << " " ; } // Driver Code int main() { int n = 6, g = 5; generateSequence(n, g); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to print the required sequence static void generateSequence( int n, int g) { for ( int i = 1 ; i <= n; i++) System.out.print(i * g + " " );; } // Driver Code public static void main(String []args) { int n = 6 , g = 5 ; generateSequence(n, g); } } // This code is contributed by Rituraj Jain |
Python3
# Python3 implementation of the approach # Function to print the required sequence def generateSequence(n, g): for i in range ( 1 , n + 1 ): print (i * g, end = " " ) # Driver Code if __name__ = = "__main__" : n, g = 6 , 5 generateSequence(n, g) # This code is contributed by Rituraj Jain |
C#
// C# implementation of the approach using System ; class GFG { // Function to print the required sequence static void generateSequence( int n, int g) { for ( int i = 1; i <= n; i++) Console.Write(i * g + " " ); } // Driver Code public static void Main() { int n = 6, g = 5; generateSequence(n, g); } } // This code is contributed by Ryuga |
PHP
<?php // PHP implementation of the approach // Function to print the required sequence function generateSequence( $n , $g ) { for ( $i = 1; $i <= $n ; $i ++) echo $i * $g . " " ; } // Driver Code $n = 6; $g = 5; generateSequence( $n , $g ); // This code is contributed by ita_c ?> |
Javascript
<script> // Javascript implementation of the approach // Function to print the required sequence function generateSequence(n, g) { for ( var i = 1; i <= n; i++) { document.write(i*g+ " " ); } } // Driver Code var n = 6, g = 5; generateSequence(n, g); </script> |
5 10 15 20 25 30
Time Complexity: O(n)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!