HackerRank: Happiness Score

Problem Statement

Summer is coming!

When you travel, you always plan ahead. You have shortlisted N cities to travel. Each city has distinct integer id from 1 to N. Each city also has a satisfaction score associated with it. If you travel to a city you will get the satisfaction score. Your “Happiness Score” is the sum of all the satisfaction scores from all the cities you’ve travelled to.

You have a passion for numbers – especially prime numbers. You want to know how many possible unique prime numbers you can get as “Happiness Score” by visiting any subset (possibly some or all) of the N cities.

Input Format

First line will be an integer denoting number of cities. Second line will have satisfaction score SiSi for all the cities from 1 to N.

Notes

  • 1<=N<=18
  • 1<=Si<=100000
  • A prime number is a natural number greater than 1 which has no positive divisors other than 1 and itself.

Output Format

Output should be an integer number denoting how many possible Happiness Scores you can get which are prime numbers.

Sample Input

3
3 2 6

Sample Output

4

Explanation

You can achieve “Happiness Scores” 3, 2, (3+2), (3+2+6) , where all of them are prime numbers. Here 2, 3 , 5, 11 are prime numbers.

Solution