Why is my output "4 10 7" instead of "4 3 10 7" when i write the following code

Question

I am trying to count the number of set bits are present in a number and arranging the numbers in the ascending order according to the count of the set bits.

My input is :

1
4
3 4 7 10

Expected Output is:

4 3 10 7

My output is:

4 10 7

Why is it skipping 3 when displaying?

package practice;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.HashMap;
import java.util.TreeMap;
public class MonkAndTasks {
    public static void main(String args[]) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        int k = 0;

        while (k < t) {
            long n = Long.parseLong(br.readLine());
            String str = br.readLine();
            String ar[] = str.split(" ");
            int i = 0;
            HashMap<Integer,Long> hm = new HashMap<Integer,Long>();
            while (i < n) {
                Long a = Long.parseLong(ar[i++]);
                hm.put(count(a), a);
            }
            TreeMap<Integer,Long> tm = new TreeMap<Integer,Long>(hm);
            Collection < Long > c = tm.values();
            for (Long e: c) {
                System.out.print(e + " ");
            }
            System.out.println();
        }
    }

    static int count(Long n) {
        int c = 0;
        while (n > 0) {
            n = n & (n - 1);
            c++;
        }
        return c;
    }
}

When I print the value a to check whether a reads the value 3 or not, it turns out that it is reading the value 3 but after passing value to hashmap and treemap yet the desired output is not displayed.

Answer 1

You are putting the 4 numbers (4 3 10 7) as values in a TreeMap where the key seems to be the number of 1 bits (I think that's what static int count(Long n) does). 3 and 10 both have 2 1 bits (11 and 1010 respectively), so 10 replaces 3 in the Map (since a Map doesn't allow duplicate keys), and 3 is never output.

Basically, the following loop

while(i<n)
{   
    Long a=Long.parseLong(ar[i++]);
    hm.put(count(a),a);
}

inserts the following entries to the TreeMap :

hm.put(1,4);
hm.put(2,3);
hm.put(2,10); // this entry has the same key as the previous entry and therefore
              // replaces it
hm.put(3,7);