System generated Social Network

Question

In a particular social network friends are automatically allocated to users by the system and users cannot add friends of their choice on their own. There are currently N users on the social network, labeled from 2 to N+1.

For every ith user (where i ranges from 2 to N+1), the system allocated all the users labeled with multiples of i as the user's friends (if possible).

One day, all users of the social network come together for a meeting and form groups such that each person in a group is a direct friend or a friend of friend of every other person of that group.

Find the total number of groups.

Input Specifications:

Input1: N, denoting the number of users on the social network

Output Specification: your function should return the number of groups that can be formed on given conditions

Example 1:

Input1: 5 Output: 2

Explanation: Two groups will be formed

2,3,4,6
5

Example 2:

Input1: 10 Output: 3

Explanation: Three groups will be formed:

2,3,4,5,6,8,9,10
7
11

Solution suggestions

Please optimize my solution. My solution is working perfectly but doesn't look optimal.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.Set;

public class SocialNetwork {

    public static void main(String[] args) {
        InputStreamReader r = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(r);
        int value = 0;

        try {
            value = Integer.parseInt(br.readLine());
        } catch (IOException e) {
            System.out.println(e.getMessage());
        }

        HashMap<Integer, List<Integer>> map = new HashMap<>();

        for (int i = 2; i <= value + 1; i++) {

            List<Integer> list = new ArrayList<>();

            for (int j = 1; j * i <= value + 1; j++) {
                int tempValue = j * i;

                list.add(tempValue);

                if (i != tempValue) {
                    List<Integer> addedList = map.get(tempValue);

                    if (addedList == null) {
                        addedList = new ArrayList<>();
                    }

                    if (!addedList.contains(i)) {
                        addedList.add(i);
                        map.put(tempValue, addedList);
                    }
                }
            }

            List<Integer> currList = map.get(i);
            if (currList != null)
                currList.addAll(list);
            else
                currList = list;

            map.put(i, currList);
        }

        // Iterate through all elements of map

        Iterator<Entry<Integer, List<Integer>>> iterator = map.entrySet().iterator();

        List<Integer> visitedKeys = new ArrayList<>();

        List<Set<Integer>> listSet = new ArrayList<>();

        while (iterator.hasNext()) {
            Entry<Integer, List<Integer>> entry = iterator.next();
            Integer key = entry.getKey();
            List<Integer> keyValue = entry.getValue();

            if (visitedKeys.contains(key)) {
                continue;
            }

            Set<Integer> setItem = new HashSet<>();
            updateSet(key, keyValue, visitedKeys, map, setItem);

            listSet.add(setItem);
        }

        System.out.println("groups=" + listSet);
        System.out.println("Number of groups=" + listSet.size());
    }

    private static void updateSet(Integer key, List<Integer> keyValue, List<Integer> visitedKeys,
            HashMap<Integer, List<Integer>> map, Set<Integer> setItem) {

        for (Integer item : keyValue) {

            if (visitedKeys.contains(item)) {
                continue;
            }

            if (!item.equals(key)) {
                List<Integer> mapVal = map.get(item);
                if (mapVal != null) {
                    updateSet(item, mapVal, visitedKeys, map, setItem);
                }
            }

            visitedKeys.add(item);

            setItem.add(item);
        }
    }
}

dariosicily · Accepted Answer · 2020-03-31 21:32:08Z

I start from mathematical consideration using one of the examples you provided:

Input: 10 output: 3

2,3,4,5,6,8,9,10
7
11

All the elements multiple of 2 are in the set containing 2, the other sets will always contain just one prime number like {7} and {11} : if it were not so the number would be not prime and would be contained in another previous set.

So instead of using the structure :

HashMap<Integer, List<Integer>> map = new HashMap<>();

It is better to use a List of Set considering that the set containing number 2 will be always present:

List<Set<Integer>> list = new ArrayList<>();
Set<Integer> set = new HashSet<>();
set.add(2);
list.add(set);

You can dismiss numbers multiple of 2 so you can use a loop starting from number 3 and with an increment of 2, so if you examining numbers from 3 to n included you can write:

public static List<Set<Integer>> createGroups(int n) {
    List<Set<Integer>> list = new ArrayList<>();
    Set<Integer> set = new HashSet<>();
    set.add(2);
    list.add(set);
    for (int i = 3; i <= n; i += 2) {
            //here your logic
    }
    return list;
}

About the core of the loop if you have an odd number i so that i * 2 <= n , you are sure it will be contained in the set including number 2, like below:

if (i * 2 <= n) {
    list.get(0).add(i); <-- it is the set containing 2
}

Otherwise you will check if one of the previously created sets contain a value dividing your number and add the number to this set if existing, for these you can use helper methods:

private static boolean isDivisor(int n, Set<Integer> set) {
    for (int elem : set) {
        if (n % elem == 0) {
            return true;
        }
    }
    return false;
}

private static boolean addedToOneSet(int n, List<Set<Integer>> list) {
    for (Set<Integer> set : list) {
        if (isDivisor(n, set)) { 
            set.add(n);
            return true;
        }
    }
    return false;
}

The code of the method will include these helper functions:

public static List<Set<Integer>> createGroups(int n) {
    List<Set<Integer>> list = new ArrayList<>();
    Set<Integer> set = new HashSet<>();
    set.add(2);
    list.add(set);
    for (int i =  3; i <= n; i += 2) {
        if (i * 2 <= n) {
            list.get(0).add(i);
        } else {
            if (!addedToOneSet(i, list)) {
                Set<Integer> newset = new HashSet<>();
                newset.add(i);
                list.add(newset);
            }
        }
    }
    return list;
}

Now the code of the class with some tests:

public class SocialNetwork {

    private static boolean isDivisor(int n, Set<Integer> set) {
        for (int elem : set) {
            if (n % elem == 0) {
                return true;
            }
        }
        return false;
    }

    private static boolean addedToOneSet(int n, List<Set<Integer>> list) {
        for (Set<Integer> set : list) {
            if (isDivisor(n, set)) { 
                set.add(n);
                return true;
            }
        }
        return false;
    }

    public static List<Set<Integer>> createGroups(int n) {
        List<Set<Integer>> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        set.add(2);
        list.add(set);
        for (int i =  3; i <= n; i += 2) {
            if (i * 2 <= n) {
                list.get(0).add(i);
            } else {
                if (!addedToOneSet(i, list)) {
                    Set<Integer> newset = new HashSet<>();
                    newset.add(i);
                    list.add(newset);
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        System.out.println(createGroups(6)); //<-- [[2, 3], [5]]
        System.out.println(createGroups(11)); //<-- [[2, 3, 5, 9], [7], [11]]
        System.out.println(createGroups(20)); //<-- [[2, 3, 5, 7, 9, 15], [11], [13], [17], [19]]

    }

}

The sizes of the lists (the groups) are the solution to the problem.

Stack Exchange Network

System generated Social Network

1 Answer 1

You must log in to answer this question.

Hot Network Questions

System generated Social Network

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions