posted 2 years ago

I was trying to solve a programming puzzle here, and i wrote to codes with same logic but different data structures. They are as follow.

and

The second code where i use ArrayList worked only for two test cases but the one where i used arrays worked for all cases.Here are the outupts of my codes output1 and output2 respectively. Can anyone please explain why this is happening even when i am using the same logic.

and

The second code where i use ArrayList worked only for two test cases but the one where i used arrays worked for all cases.Here are the outupts of my codes output1 and output2 respectively. Can anyone please explain why this is happening even when i am using the same logic.

Stephan van Hulst

Saloon Keeper

Posts: 7991

143

posted 2 years ago

You're not performing the same logic. p.get(i) returns an Integer, not an int. In your first program you perform int comparison, in your second program you perform object comparison. For values outside the range -128 to 127, == will return false for two different instances of Integer, even if they have the same value.

The solution is to use equals() instead of ==.

The solution is to use equals() instead of ==.

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

Stephan van Hulst

Saloon Keeper

Posts: 7991

143

Stephan van Hulst

Saloon Keeper

Posts: 7991

143

posted 2 years ago

The map

Regardless of where a number occurs in the array, the number of pairs of equal numbers for a specific number only depends on how many times that specific number occurs: It doesn't matter if the array holds [1, 1, 2] or [1, 2, 1]; the number of pairs you can make with a 1 is the same: 3.

1 occurrence means 1 pair.

2 occurrences mean 3 pairs.

3 occurrences mean 6 pairs.

4 occurrences mean 10 pairs.

1, 3, 6, 10... etc. are called

So what line 18 does is stream the values (the number of occurrences of the key) of the map, for each number of occurrence

`occurrences`keeps track how much each number occurs in the array. The loop containing line 15 fills this map. The merge function is a convenient way of setting the number of occurrences to 1 if the number hasn't been encountered before, and increments the count by 1 if it has been encountered before.Regardless of where a number occurs in the array, the number of pairs of equal numbers for a specific number only depends on how many times that specific number occurs: It doesn't matter if the array holds [1, 1, 2] or [1, 2, 1]; the number of pairs you can make with a 1 is the same: 3.

1 occurrence means 1 pair.

2 occurrences mean 3 pairs.

3 occurrences mean 6 pairs.

4 occurrences mean 10 pairs.

1, 3, 6, 10... etc. are called

*Triangle Numbers*. An easy way to calculate the nth triangle number is with the formula`n(n+1)/2`.So what line 18 does is stream the values (the number of occurrences of the key) of the map, for each number of occurrence

`x`, transform it to the number of pairs using the triangle number formula, and finally sum all the numbers of pairs.
Stephan van Hulst

Saloon Keeper

Posts: 7991

143