white_square's blog

Need help with B-181
By white_square, history, 2 years ago, In English

Question:- 181B - Number of Triplets

Question

Solution that got accepted-: 178183074

Solution that got rejected-: 178183367

Other solution using same concept

Summary: The logic of both code is same, I've tried using HashMap and HashSet but the solution does not work.

I do not understand why don't the code using HasHmap/HashSet work.

Any help is appreciated.

Thank you.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

String-based HashSet? Bad idea... The string formed by the numbers 1 and 23 is the same as the string formed by the numbers 12 and 3 — you can guess how this can go terribly wrong.

A HashMap / HashSet solution is easily possible by using a unique concatenation of numbers. Example: if the numbers are between -1000 and 1000, then you can artificially add 1000 to make them positive and then set: key = number1 * 2001 + number2. Thus, the key's remainder when divided by 2001 is definitely number2+1000, and its quotient is definitely number1+1000.

(Your frequency array solution does exactly this while also making use of the fact that the bounds on numbers are relatively small.)

TL;DR avoid string-based concatenation of numbers

→ Reply