We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. New Year Present

New Year Present

Problem
Submissions
Leaderboard
Discussions
Editorial

Nina received an odd New Year's present from a student: a set of unbreakable sticks. Each stick has a length, , and the length of the stick is . Deciding to turn the gift into a lesson, Nina asks her students the following:

How many ways can you build a square using exactly of these unbreakable sticks?

Note: Two ways are distinct if they use at least one different stick. As there are choices of sticks, we must determine which combinations of sticks can build a square.

Input Format

The first line contains an integer, , denoting the number of sticks. The second line contains space-separated integers describing the length of each stick in the set.

Constraints

Output Format

On a single line, print an integer representing the number of ways that unbreakable sticks can be used to make a square.

Sample Input 0

8
4 5 1 5 1 9 4 5 

Sample Output 0

3

Sample Input 1

6
1 2 3 4 5 6 

Sample Output 1

0    

Explanation

Sample 0
Given sticks (), the only possible side length for our square is . We can build square in different ways:

In order to build a square with side length using exactly sticks, and must always build two of the sides. For the remaining two sides, you must choose of the remaining sticks of length ( and ).

Sample 1
We have to use all sticks, making the largest stick length () the minimum side length for our square. No combination of the remaining sticks can build more sides of length (total length of all other sticks is and we need at least length ), so we print .

Author

allllekssssa

Difficulty

Hard

Max Score

80

Submitted By

670

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature