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 #156: Counting Digits

Project Euler #156: Counting Digits

Problem
Submissions
Leaderboard
Discussions

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

Starting from zero the natural numbers are written down in base like this: ....

Consider the digit . After we write down each number , we will update the number of ones that have occurred and call this number . The first values for , then, are as follows:

Note that never equals .

So the first two solutions of the equation are and . The next solution is .

In the same manner the function gives the total number of digits that have been written down after the number has been written.

In fact, for every digit , is the first solution of the equation .

Let be the sum of all the solutions for which .

You are given base and the set of digits in base . Find for numbers written in base .

Note: if, for some , for more than one value of this value of is counted again for every value of for which .

Input Format

First line of each test contains two integers: and - base and the cardinal number of . Second line contains distinct space-separated digits in base .

Constraints

Output Format

Output a single number which is the answer to the problem.

Sample Input

2 1
1

Sample Output

3

Explanation

There are two solutions where which are and . Starting from .

Author

bayleef

Difficulty

Medium

Max Score

100

Submitted By

345

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
  • Request a Feature