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. All Contests
  2. ProjectEuler+
  3. Project Euler #158: Exploring strings

Project Euler #158: Exploring strings

Problem
Submissions
Leaderboard
Discussions

This problem is a programming version of Problem 158 from projecteuler.net

Taking three different letters from the letters of the alphabet, character strings of length three can be formed.

Examples are abc, hat and zyx.

When we study these three examples we see that for abc two characters come lexicographically after its neighbour to the left.

For hat there is exactly one character that comes lexicographically after its neighbour to the left. For zyx there are zero characters that come lexicographically after its neighbour to the left.

In all there are strings of length for which exactly one character comes lexicographically after its neighbour to the left.

We now consider strings of different characters from some foreign alphabet consisting of characters. For every , is the number of strings of length for which exactly characters come lexicographically after their neighbour to the left.

For what is the maximum value of ?

Input Format

The first line of each test contains two integers: and which is the size of alphabet and the number of queries.
On the next line there are different numbers separated by single spaces given by .

Constraints



Output Format

Output one number i.e. .

Sample Input

2 2
0 1

Sample Output

3

Explanation

Let's assume our alphabet contains only letters 'A' and 'B'. Then we have the following values for :

(both words "A" and "B")
(word "BA")
(word "AB")

We now see that the maximum for is and the maximum for is .

Author

bayleef

Difficulty

Medium

Max Score

100

Submitted By

94

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

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