Buy a Shovel Coding Question-Codeforces rated 800

Problem Statement :

Polycarp urgently needs a shovel! He comes to the shop and chooses an appropriate one. The shovel that Polycarp chooses is sold for k burles. Assume that there is an unlimited number of such shovels in the shop.

In his pocket, Polycarp has an unlimited number of “10-burle coins” and exactly one coin of r burles (1 ≤ r ≤ 9).

What is the minimum number of shovels Polycarp has to buy so that he can pay for the purchase without any change? It is obvious that he can pay for 10 shovels without any change (by paying the required amount of 10-burle coins and not using the coin of r burles). But perhaps he can buy fewer shovels and pay without any change.

Note that Polycarp should buy at least one shovel.

Input Format:

The single line of input contains two integers k and r (1 ≤ k ≤ 1000, 1 ≤ r ≤ 9) — the price of one shovel and the denomination of the coin in Polycarp’s pocket that is different from “10-burle coins”.

Remember that he has an unlimited number of coins in the denomination of 10, that is, Polycarp has enough money to buy any number of shovels.

Output Format:

Print the required minimum number of shovels Polycarp has to buy so that he can pay for them without any change.


117 3



Explanation of Test Case:

In the given example Polycarp can buy 9 shovels and pay 9*117 = 1053 burles. Indeed, he can pay this sum by using 10-burle coins and one 3-burle coin. He can’t buy fewer shovels without any change.


Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.




Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

An Insight into MongoDB Sharding Chunk Splitting and Migration

Unlocking the Power of DSLs: Stateless State Machines

Adding HTML support to UITextView with custom CSS.

Comparing architectural aspects of distributed systems- Part 1

Performance Profiling in Python

(python3) LeetCode (1) Two Sum

Building a personal website on GIT

Business Agility Requires More Than Organizational Stability

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store


Upskilling students for tech placements!

More from Medium

Add Odd or Subtract Even Coding Question

The Top 10 Algorithms Programmers Should Know In Graph Data Structure

LeetCode 489 — Robot Room Cleaner (Roomba)

Monotonic Stack Problems