Problem Statement:
Given an Array A of size N and P number of pairs describing groups that can be formed between this two pairs( pairs are indices & 1 based indexing) of the pair,the task is to find the group which has the maximum sum.Print its indices(1 based indexing).
Note:If any element is not mentioned in any pair than it forms its own individual single group.Groups can only be formed between the input pairs.If two or more groups has same sum output the one having less elements.
Example:
input:N=5
A=[23,43,123,54,2]
P=3
pair 1:1 3
pair 2:2 3
pair 3:1 2
output:(1,2,3)
Explanation:In the given input there are 3 pairs (1,3)i.e 1 & 3 can be in one group ,(2,3) i.e 2 & 3 can be in one group,(1,2) i.e 1 & 2 can be in one group.Combining this we can say that (1,2,3) will be in same group.4 and 5 is not mentioned in any group this means that they form their individual single group.So,there are total 3 groups Group 1(1,2,3) whose sum is 189, Group 2 (4) whose sum is 54, Group 3 (5) whose sum is 2.So (1,2,3) has maximum sum.
input:N=5
A=[10,10,10,15,15]
P=3
pair 1:1 2
pair 2:1 3
pair 3:4 5
output:(4,5)
Explanation:Group 1 -> (1,2,3) =>sum = 30 Group 2-> (4,5) => sum = 30 second group has lesser elements
input:N=8
A[3,4,1,2,9,8,7,5]
P=5
pair 1:1 2
pair 2:3 4
pair 3:5 6
pair 4:7 8
pair 5:2 6
output:(1,2,5,6)
explanation:Group 1->(1,2,5,6) => sum = 24 Group 2->(3,4) => sum = 3 Group 3->(7,8) => sum = 12
Approach:Our main task is to know which indices occurs in same group.If we can know that which indices occurs in same group then we can easily find the group with maximum sum.To find the indices which occurs in same group we can use an Array B of size N & then initialize it with -1.In the array B, B[i] denotes the group in which ith element is lying.If any element of array B is -1,it means that element does not occur in any group.
 |
| Before making the group |
1) Pair 1:(1,3) let us group it in group 1
2)Pair 2:(2,3) We will check if any of the 2 indices forms group earlier.Index 2 does not occur in any group but index 3 forms group 1,so index 2 will also occur in group 1.
 |
| Allotting elements to group one by one |
3)Index 4 and index 5 will form its own individual group 2 & respectively.
 |
| After allotting all elements to respective groups |
Below is the implementation of the above approach:
Code
// Java program to find the maximum sum group
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
class GFG {
// function to find the group with maximum sum
public static void findgroup(long[] a,ArrayList<Integer> pairs,int p, int n)
{
// duplicate array to find which index occurs in
// which group
int[] b = new int[n];
// initialize array with -1
Arrays.fill(b, -1);
// variable to make group no
int grpno = 1;
// finding the pairs stored in list
for (int i = 0; i < pairs.size(); i += 2) {
// first index of the pair
int one = pairs.get(i);
// second index of the pair
int two = pairs.get(i + 1);
// if both index doesnot already forms group
// then
// make them in new group with group no
if (b[one - 1] == -1 && b[two - 1] == -1) {
b[one - 1] = grpno;
b[two - 1] = grpno;
grpno++;
}
// if anyone of both index forms group then
// make this pair with older group
else {
if (b[one - 1] != -1) {
int old = b[two - 1];
b[two - 1] = b[one - 1];
for (int k = 0; k < n; k++) {
if (old != -1 && b[k] == old) {
b[k] = b[one - 1];
}
}
}
else {
int old = b[one - 1];
b[one - 1] = b[two - 1];
for (int k = 0; k < n; k++) {
if (old != -1 && b[k] == old) {
b[k] = b[two - 1];
}
}
}
}
}
// make all ungrouped index to grouped index
for (int i = 0; i < n; i++) {
if (b[i] == -1) {
b[i] = grpno;
grpno++;
}
}
// finding group with maximum sum
HashMap<Integer, Long> map = new HashMap<>();
for (int i = 0; i < n; i++) {
Long k = map.get(b[i]);
map.put(b[i], (k == null) ? a[i] : k + a[i]);
}
long maxsum = Long.MIN_VALUE;
for (Map.Entry<Integer, Long> e : map.entrySet()) {
maxsum = Math.max(maxsum, e.getValue());
}
// adding all those group no whose sum is maximum
ArrayList<Integer> li = new ArrayList<>();
for (Map.Entry<Integer, Long> e : map.entrySet()) {
if (e.getValue() == maxsum) {
li.add(e.getKey());
}
}
// if there is only one group which has maximum sum
if (li.size() == 1) {
// printing the result
for (int i = 0; i < n; i++) {
if (b[i] == li.get(0)) {
System.out.print((i + 1) + " ");
}
}
System.out.println();
}
// fimd the group which has max sum with lesser
// elementts
else {
int minct = Integer.MAX_VALUE;
int minval = Integer.MAX_VALUE;
for (int i = 0; i < li.size(); i++) {
int va = li.get(i);
int ct = 0;
for (int j = 0; j < n; j++) {
if (b[j] == va) {
ct++;
}
}
if (ct < minct) {
minct = ct;
minval = va;
}
}
// printing the result
for (int i = 0; i < n; i++) {
if (b[i] == minval) {
System.out.print((i + 1) + " ");
}
}
System.out.println();
}
}
//driver code
public static void main(String[] args)
{
//array size
int n = 5;
//array elements
long[] a = { 23, 43, 123, 54, 2 };
//number of pairs
int p = 3;
// adding all pair indices in list
ArrayList<Integer> pairs = new ArrayList<>();
pairs.add(1);
pairs.add(3);
pairs.add(2);
pairs.add(3);
pairs.add(1);
pairs.add(2);
//function call
findgroup(a, pairs, p, n);
}
}
Output:
1 2 3
Time complexity:O(p*n)
Feel free to comment if you have any doubt in comments section
For more Data structure and algorithms,computer science,programming,coding related problems search my website.
Learn how to prepare for Information Technology Based companies here
0 Comments
Have any doubt ? contact us