Tag: network

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

For each i-th user (where i varies from 2 to N + 1), the system assigned all users tagged with multiples of i as user friends (if possible).

One day, all users of the social network get together for a meeting and form groups so that each person in a group is a direct friend or a friend of anyone else in that group.

Find the total number of groups.

Input Specifications:

Entry 1: N, which indicates the number of users in the social network

Output specification:
your function should return the number of groups that can be formed under certain conditions

Example 1:

Entry1: 5
Output: 2

Explanation:
Two groups will be formed.

2,3,4,6
5

Example 2

Entry1: 10
Output: 3

Explanation:
Three groups will be formed:

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

Suggestions for solutions

Please optimize my solution. My solution works perfectly but it 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> map = new HashMap<>();

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

            List list = new ArrayList<>();

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

                list.add(tempValue);

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

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

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

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

            map.put(i, currList);
        }

        // Iterate through all elements of map

        Iterator>> iterator = map.entrySet().iterator();

        List visitedKeys = new ArrayList<>();

        List> listSet = new ArrayList<>();

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

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

            Set 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 keyValue, List visitedKeys,
            HashMap> map, Set setItem) {

        for (Integer item : keyValue) {

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

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

            visitedKeys.add(item);

            setItem.add(item);
        }
    }
}