Live Batches
Masterclasses
Menu
Free Courses
Account
Login / Sign Up

Stepping Numbers

Medium Acceptance 48.44% Points 30.00

A number is considered a stepping number if the absolute difference between every two consecutive digits is exactly 1. For example, '321' is a stepping number, but '421' is not. Given two integers n and m, your task is to find the total count of all stepping numbers in the range [n, m].

Your task is to complete the function steppingNumbers() which takes the integer n and integer m as input parameters and returns the number of stepping numbers in the range between n and m.

Examples
Example 1

Example 1

Input: n = 0, m = 21

Output: 13

Explanation: Stepping no's are 0 1 2 3 4 5 6 7 8 9 10 12 21

Example 2

Example 2

Input: n = 10, m = 15

Output: 2

Explanation: Stepping no's are 10, 12

Hints
Hint 1
Expected Time Complexity: O(log(M))
Hint 2
Expected Auxiliary Space: O(SN) where SN is the number of stepping numbers in the range
Constraints
  • 0 = N < M = 10^7
Companies
Amazon
Topics
BFS DFS
Solution.cs C#JavaPythonC++Javascript

Unlock the code editor

Sign in to write, run, and submit your solution against the full test suite.

  • Run code against sample & hidden test cases
  • Save submissions and track your streak
  • Compare with editorial & community solutions