Given an array A containing N elements (N is divisible by 3), the task is to split the numbers into groups of 3, let the group have 3 elements X1, X2, and X3, the following conditions should be true for the group:
- X1, X2, and X3 are pairwise distinct
- X3 is divisible by X2
- X2 is divisible by X1
Print -1 if splitting the array into N/3 Such groups is not possible.
Note: Elements of the array will lie in the range 1 to 6 (inclusive).
Examples:
Input : N = 6, A[] = {2, 2, 1, 1, 4, 6}
Output : 1 2 4
1 2 6
Explanation:
Group 1: Pairs = {(1,2), (2,4), (1,4)}
All pairs are distinct,
4 is divisible by 2 and 2 by 1.
Group 2: Pairs = {(1,2), (2,6), (1,6)}
All pairs are distinct,
6 is divisible by 2 and 2 by 1.
Input : N = 6, A[] = {1, 1, 1, 6, 6, 3}
Output : -1
Approach:
Since the values of the array are between 1 and 6, only the following kind of groups can be made:
- 1 2 4
- 1 2 6
- 1 3 6
Start of by counting the frequency of each element. Since 1 is common across all groups, it must occur exactly N/3 times. 4 can be put into only the first kind of group, which always contains 2. So the count of 2 should be greater than the count of 4. The remaining 2 can be put in only the second kind of groups. Now, the remaining numbers have to be put in the third kind of groups. If at any point the count is less than required, the answer would be -1.
Below is the implementation of the above approach:
C++
// C++ program to split array in groups of 3#include <bits/stdc++.h>using namespace std;// Function to print the groups after// splitting array in groups of 3void printGroups(int n, int a[]){ int ct[7] = { 0 }, grps = n / 3, i; // Count occurrence of each element for (i = 0; i < n; i++) ct[a[i]]++; // Check if it is possible to form the groups if (ct[1] != grps || (ct[4] + ct[6]) != grps || (ct[2] + ct[3]) != grps || ct[4] > ct[2]) { cout << -1; return; } // Print groups that end at 4 for (i = 0; i < ct[4]; i++) cout << "1 2 4\n"; // Print groups that end at 6, with 2 // in the middle for (i = 0; i < ct[2] - ct[4]; i++) cout << "1 2 6\n"; // Print groups that have a 3 in the middle for (i = 0; i < ct[3]; i++) cout << "1 3 6\n";}// Driver Codeint main(){ int n = 6; int a[n] = { 2, 2, 1, 1, 4, 6 }; printGroups(n, a); return 0;} |
Java
// Java program to split array in groups of 3class GFG { // Function to print the groups after // splitting array in groups of 3 static void printGroups(int n, int a[]) { int ct[] = new int[7], grps = n / 3, i; // Count occurrence of each element for (i = 0; i < n; i++) { ct[a[i]]++; } // Check if it is possible to form the groups if (ct[1] != grps || (ct[4] + ct[6]) != grps || (ct[2] + ct[3]) != grps || ct[4] > ct[2]) { System.out.print(-1); return; } // Print groups that end at 4 for (i = 0; i < ct[4]; i++) { System.out.print("1 2 4\n"); } // Print groups that end at 6, with 2 // in the middle for (i = 0; i < ct[2] - ct[4]; i++) { System.out.print("1 2 6\n"); } // Print groups that have a 3 in the middle for (i = 0; i < ct[3]; i++) { System.out.print("1 3 6\n"); } } // Driver Code public static void main(String[] args) { int n = 6; int a[] = {2, 2, 1, 1, 4, 6}; printGroups(n, a); }}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 program to split array in # groups of 3# Function to print the groups after# splitting array in groups of 3def printGroups(n, a): ct = [0 for i in range(7)] grps = n // 3 i = 0 # Count occurrence of each element for i in range(n): ct[a[i]] += 1 # Check if it is possible to # form the groups if (ct[1] != grps or (ct[4] + ct[6]) != grps or (ct[2] + ct[3]) != grps or ct[4] > ct[2]): print(-1) return # Print groups that end at 4 for i in range(ct[4]): print("1 2 4") # Print groups that end at 6, with 2 # in the middle for i in range(ct[2] - ct[4]): print("1 2 6") # Print groups that have a 3 in the middle for i in range(ct[3]): print("1 3 6")# Driver Coden = 6a = [2, 2, 1, 1, 4, 6 ]printGroups(n, a)# This code is contributed# by Mohit Kumar |
C#
// C# program to split array in groups of 3using System;class GFG { // Function to print the groups after // splitting array in groups of 3 static void printGroups(int n, int []a) { int []ct = new int[7]; int grps = n / 3, i; // Count occurrence of each element for (i = 0; i < n; i++) { ct[a[i]]++; } // Check if it is possible to form the groups if (ct[1] != grps || (ct[4] + ct[6]) != grps || (ct[2] + ct[3]) != grps || ct[4] > ct[2]) { Console.Write(-1); return; } // Print groups that end at 4 for (i = 0; i < ct[4]; i++) { Console.Write("1 2 4\n"); } // Print groups that end at 6, with 2 // in the middle for (i = 0; i < ct[2] - ct[4]; i++) { Console.Write("1 2 6\n"); } // Print groups that have a 3 in the middle for (i = 0; i < ct[3]; i++) { Console.Write("1 3 6\n"); } } // Driver Code public static void Main() { int n = 6; int []a = {2, 2, 1, 1, 4, 6}; printGroups(n, a); }}// This code is contributed // by Akanksha Rai |
PHP
<?php// PHP program to split array in groups of 3// Function to print the groups after// splitting array in groups of 3function printGroups($n, $a){ $ct = array(); $grps = $n / 3; // Count occurrence of each element for ($i = 0; $i < $n; $i++) $ct[$a[$i]]++; // Check if it is possible to form the groups if ($ct[1] != $grps || ($ct[4] + $ct[6]) != $grps || ($ct[2] + $ct[3]) != $grps || $ct[4] > $ct[2]) { echo -1; return; } // Print groups that end at 4 for ($i = 0; $i < $ct[4]; $i++) echo "1 2 4\n"; // Print groups that end at 6, with 2 // in the middle for ($i = 0; $i < $ct[2] - $ct[4]; $i++) echo "1 2 6\n"; // Print groups that have a 3 in the middle for ($i = 0; $i < $ct[3]; $i++) echo "1 3 6\n";}// Driver Code$n = 6;$a = array(2, 2, 1, 1, 4, 6);printGroups($n, $a);// This code is contributed // by Akanksha Rai?> |
Javascript
<script>// Javascript program to split array in groups of 3// Function to print the groups after// splitting array in groups of 3function printGroups(n, a){ let ct = new Array(7).fill(0), grps = parseInt(n / 3), i; // Count occurrence of each element for (i = 0; i < n; i++) ct[a[i]]++; // Check if it is possible to form the groups if (ct[1] != grps || (ct[4] + ct[6]) != grps || (ct[2] + ct[3]) != grps || ct[4] > ct[2]) { document.write(-1); return; } // Print groups that end at 4 for (i = 0; i < ct[4]; i++) document.write("1 2 4<br>"); // Print groups that end at 6, with 2 // in the middle for (i = 0; i < ct[2] - ct[4]; i++) document.write("1 2 6<br>"); // Print groups that have a 3 in the middle for (i = 0; i < ct[3]; i++) document.write("1 3 6<br>");}// Driver Code let n = 6; let a = [ 2, 2, 1, 1, 4, 6 ]; printGroups(n, a);</script> |
Output:
1 2 4 1 2 6
Time Complexity: O(N)
Auxiliary Space: O(1), no extra space is required, so it is a constant.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
