02.The Spice Scale

EasyMath
Pattern lockedSolve it, or make 3 submissions, to unlock which classic problem this story hides.
A night spice market in Old Delhi. Two sacks have the numbers 204 and 240. Their tins 0, 2 and 4 sit in the two pans of a magic scale. The scale stays straight under a green check mark.

// The story

In Old Delhi, Kavya Sethi sells sacks full of small spice tins. Every sack has a number on it. Inside, there is one tin for each digit of that number.

Kavya swaps two sacks only if they have the same tins. They must have the same digits, and each digit must come the same number of times. The order does not matter. Some sacks also have a red stamp, which means the number is negative. A sack with a red stamp can only be swapped for another sack with a red stamp.

Kavya empties the two sacks into the two pans of her magic scale. It does not weigh the tins. It stays straight only when the swap is fair. Tonight many traders have come, and the scale is too slow. Write a program that does this check for her.

// Your task

You get the two sack numbers x and y. Return true if the swap is fair (the scale stays straight). Otherwise, return false (one side goes down).

Input: two lines, x then y. Limits: -109 ≤ x, y ≤ 109.

  • A sack has one tin for each digit of its number. The minus sign is not a digit. 100 has the tins 1, 0 and 0. 0 has one tin: 0.
  • The swap is fair when each digit from 0 to 9 comes the same number of times in x and in y. The order of the digits does not matter.
  • The stamps must match. Both numbers must be negative, or both must not be negative. A negative number and a positive number (or 0) never match. So -123 and 321 give false. But -123 and -321 give true.

Example 1:

Input:
204
240

Output:
true

Both sacks have the tins 0, 2 and 4. The piles match, so the scale stays straight.

Example 2:

Input:
23
959

Output:
false

One sack has the tins 2 and 3. The other has 5, 9 and 9. The piles are different, so one side goes down.

Example 3:

Input:
-123
-321

Output:
true

Both sacks have a red stamp. Both have the tins 1, 2 and 3. So the scale stays straight.

// Constraints

  • -10^9 ≤ x, y ≤ 10^9

Time limit: 1s ·  Memory limit: 256 MB

Hint 1

First look at the stamps. If only one of the two numbers is negative, the answer is always false. After that, only the digits matter.

Hint 2

Make a count for each digit 0 to 9. Add 1 for each digit of the first number. Subtract 1 for each digit of the second number. At the end, every count must be 0.

Hint 3

Remove the minus sign first (use the absolute value). Then n % 10 gives the last digit, and n / 10 removes it. Be careful with 0: it has one tin, so your loop must count it once.

Solution.java
Sample tests