Given a number N. The task is to group all the numbers from 1 to N such GCD of all the numbers in each group is 1 as the number of groups must be minimized.
Example:
Input: N = 3
Output:
1 2 3
Explanation:
gcd(1, 2, 3) = 1Input: N = 6
Output:
1 2
3 4
5 6
Explanation:
gcd(1, 2) = 1
gcd(3, 4) = 1
gcd(5, 6) = 1
Approach: As we know, the fact that GCD of every consecutive number is 1. So we will use this fact to solve this problem. Below are the steps:
- If the number is 3, then only one group is possible {1, 2, 3} whose GCD(1, 2, 3) is 1.
- Else Iterate(say i) over [1, N/2] and form groups using (2*i – 1, 2*i) and store them in Array of Vectors(say arr[][]).
- The groups stored in the arr[][] are the desired groups.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print the groups void printGroups(vector< int > A[], int N) { // Iterate over [1, N/2]; for ( int i = 1; i <= N / 2 + 1; i++) { // Print all pairs for ( int j = 0; j < A[i].size(); j++) { cout << A[i][j] << ' ' ; } cout << endl; } } // Function to form a groups with GCD 1 void formGroups( int N) { int i; // Corner case if (N == 3) { cout << "1 2 3" ; return ; } // Array of vectors to store the // possible pairs vector< int > arr[N / 2 + 2]; for (i = 1; i <= N / 2; i++) { // Push the pair (2*i - 1, 2*i) arr[i].push_back(2 * i - 1); arr[i].push_back(2 * i); } // If N is odd then push the // last element N if (N & 1) { arr[i].push_back(N); } // Function Call printGroups(arr, N); return ; } // Driver Code int main() { int N = 10; // Function Call formGroups(N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to print the groups static void printGroups(Vector<Integer> A[], int N) { // Iterate over [1, N/2]; for ( int i = 1 ; i <= N / 2 + 1 ; i++) { // Print all pairs for ( int j = 0 ; j < A[i].size(); j++) { System.out.print(A[i].get(j) + " " ); } System.out.println(); } } // Function to form a groups with GCD 1 static void formGroups( int N) { int i; // Corner case if (N == 3 ) { System.out.print( "1 2 3" ); return ; } // Array of vectors to store the // possible pairs @SuppressWarnings ( "unchecked" ) Vector<Integer> []arr = new Vector[N / 2 + 2 ]; for ( int k = 0 ; k < arr.length; k++) arr[k] = new Vector<Integer>(); for (i = 1 ; i <= N / 2 ; i++) { // Push the pair (2*i - 1, 2*i) arr[i].add( 2 * i - 1 ); arr[i].add( 2 * i); } // If N is odd then push the // last element N if ((N & 1 ) != 0 ) { arr[i].add(N); } // Function call printGroups(arr, N); return ; } // Driver Code public static void main(String[] args) { int N = 10 ; // Function call formGroups(N); } } // This code is contributed by Rohit_ranjan |
Python3
# Python3 program for # the above approach # Function to print the groups def printGroups(A, N): # Iterate over [1, N / 2]; for i in range ( 0 , N / / 2 ): # Print all pairs for j in range ( len (A[i])): print (A[i][j], end = ' ' ) print () # Function to form a # groups with GCD 1 def formGroups(N): # Corner case if (N = = 3 ): print ( "1 2 3" ) return # Array of vectors # to store the # possible pairs arr = [] for i in range ( 1 , N / / 2 + 1 ): P = [] # Push the pair # (2 * i - 1, 2 * i) P.append( 2 * i - 1 ) P.append( 2 * i) arr.append(P) # If N is odd then push the # last element N if (N & 1 ): arr.append(N) # Function Call printGroups(arr, N) return # Driver Code if __name__ = = "__main__" : N = 10 # Function Call formGroups(N) # This code is contributed by Chitranayal |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to print the groups static void printGroups(List< int > []A, int N) { // Iterate over [1, N/2]; for ( int i = 1; i <= N / 2 + 1; i++) { // Print all pairs for ( int j = 0; j < A[i].Count; j++) { Console.Write(A[i][j] + " " ); } Console.WriteLine(); } } // Function to form a groups with GCD 1 static void formGroups( int N) { int i; // Corner case if (N == 3) { Console.Write( "1 2 3" ); return ; } // Array of vectors to store the // possible pairs List< int > []arr = new List< int >[N / 2 + 2]; for ( int k = 0; k < arr.Length; k++) arr[k] = new List< int >(); for (i = 1; i <= N / 2; i++) { // Push the pair (2*i - 1, 2*i) arr[i].Add(2 * i - 1); arr[i].Add(2 * i); } // If N is odd then push the // last element N if ((N & 1) != 0) { arr[i].Add(N); } // Function call printGroups(arr, N); return ; } // Driver Code public static void Main(String[] args) { int N = 10; // Function call formGroups(N); } } // This code is contributed by amal kumar choubey |
Javascript
<script> // Javascript program for the above approach // Function to print the groups function printGroups(A,N) { // Iterate over [1, N/2]; for (let i = 1; i <= N / 2 + 1; i++) { // Print all pairs for (let j = 0; j < A[i].length; j++) { document.write(A[i][j] + " " ); } document.write( "<br>" ); } } // Function to form a groups with GCD 1 function formGroups(N) { let i; // Corner case if (N == 3) { document.write( "1 2 3" ); return ; } // Array of vectors to store the // possible pairs let arr = new Array(Math.floor(N / 2) + 2); for (let k = 0; k < arr.length; k++) arr[k] = []; for (i = 1; i <= N / 2; i++) { // Push the pair (2*i - 1, 2*i) arr[i].push(2 * i - 1); arr[i].push(2 * i); } // If N is odd then push the // last element N if ((N & 1) != 0) { arr[i].push(N); } // Function call printGroups(arr, N); return ; } // Driver Code let N = 10; // Function call formGroups(N); // This code is contributed by avanitrachhadiya2155 </script> |
1 2 3 4 5 6 7 8 9 10
Time Complexity: O(N), where N is the given number.