fork download
copy 
  1. /*
  2.     created by: nitin23329
  3.     on Date: 09/06/21
  4. */
  5. import java.io.*;
  6. import java.util.*;
  7. /*****************************************WRITING CODE STARTS HERE******************************************/
  8.  class CodeForces {
  9.     static long [][] [] dp = new long[20][11][4];
  10.     private static void solve() {
  11.         long l = sc.nextLong();
  12.         long r = sc.nextLong();
  13.         out.println(helper(r) - helper(l-1));
  14.     }
  15.     private static long helper(long n) {
  16.         if (n <0) return 0;
  17.         if(n==0)return 1;
  18.         int digitLength = countDigitBase10(n);
  19.         int[] digitArray = new int[digitLength];
  20.         for (int i = digitLength - 1; i >= 0; i--) {
  21.             digitArray[i] = (int) (n % 10);
  22.             n /= 10;
  23.         }
  24.         for(int i=0;i<dp.length;i++)
  25.             for(int j=0;j<dp[0].length;j++)
  26.                 Arrays.fill(dp[i][j],-1);
  27.         return memo(0,10,1,0,digitArray);
  28.     }
  29.     private static long memo(int i,int prevDigit,int isBound,int isNumStarted,int[] digitArray){
  30.         if(i==digitArray.length) return 1;
  31.         int bitMast = (isBound)*(1<<1) + (isNumStarted)*(1<<0);
  32.         if(dp[i][prevDigit][bitMast]!=-1)return dp[i][prevDigit][bitMast];
  33.         int maxDigit = isBound==1? digitArray[i] : 9;
  34.         long ans = 0;
  35.         for(int digit=0;digit <= maxDigit;digit++){
  36.             if(digit == prevDigit)continue;
  37.             if(isNumStarted == 0 && digit == 0 ) ans += memo(i+1,prevDigit,(isBound==1 && digit == digitArray[i])?1:0,0,digitArray);
  38.             else ans += memo(i+1,digit,(isBound==1 && digit == digitArray[i])?1:0,1,digitArray);
  39.         }
  40.         return dp[i][prevDigit][bitMast] = ans;
  41.     }
  42.     /*****************************************WRITING CODE ENDS HERE******************************************/
  43.  
  44.     public static void main(String[] args){
  45.         FIO(false);
  46. //        FIO(true);
  47.         int testCase = 1;
  48. //        testCase = sc.nextInt();
  49.         while (testCase-- > 0) solve();
  50.         closeIO();
  51.     }
  52.  
  53.     static Scanner sc ;                     // FAST INPUT
  54.     static PrintWriter out;                // FAST OUTPUT
  55.     static PrintWriter debug ;             // DEBUG IN FILE : debug.txt
  56.  
  57.  
  58.     /**************************************HELPER FUNCTION STARTS HERE ************************************/
  59.  
  60.     public static int mod = (int) 1e9 + 7;
  61.     public static final int INT_MAX = Integer.MAX_VALUE;
  62.     public static final int INT_MIN = Integer.MIN_VALUE;
  63.     public static final long LONG_MAX = Long.MAX_VALUE;
  64.     public static final long LONG_MIN = Long.MIN_VALUE;
  65.     public static final double DOUBLE_MAX = Double.MAX_VALUE;
  66.     public static final double DOUBLE_MIN = Double.MIN_VALUE;
  67.     public static final String YES = "YES";
  68.     public static final String NO = "NO";
  69.  
  70.     public static void sort(int[] a, boolean isAscending) {
  71.         ArrayList<Integer> temp = new ArrayList<>();
  72.         for (int j : a) temp.add(j);
  73.         sort(temp, isAscending);
  74.         for (int i = 0; i < a.length; i++) a[i] = temp.get(i);
  75.     }
  76.  
  77.     public static void sort(long[] a, boolean isAscending) {
  78.         ArrayList<Long> temp = new ArrayList<>();
  79.         for (long ele : a) temp.add(ele);
  80.         sort(temp, isAscending);
  81.         for (int i = 0; i < a.length; i++) a[i] = temp.get(i);
  82.     }
  83.  
  84.     public static void sort(List list, boolean isAscending) {
  85.         if (isAscending)
  86.             Collections.sort(list);
  87.         else Collections.sort(list, Collections.reverseOrder());
  88.     }
  89.     // count the length of a number, time O(1)
  90.     public static int countDigitBase10(long n){
  91.         if(n == 0) return 0;
  92.         return (int)(1 + Math.log10(n));
  93.     }
  94.  
  95.     // euclidean algorithm
  96.     public static long gcd(long a, long b) {
  97.         // time O(max (loga ,logb))
  98.         long x = Math.min(a, b);
  99.         long y = Math.max(a, b);
  100.         if (y % x == 0) return x;
  101.         return gcd(y % x, x);
  102.     }
  103.  
  104.     public static long lcm(long a, long b) {
  105.         // lcm(a,b) * gcd(a,b) = a * b
  106.         return (a / gcd(a, b)) * b;
  107.     }
  108.  
  109.     public static long power(long x, long n) {
  110.         // time O(logn)
  111.         long ans = 1;
  112.         while (n > 0) {
  113.             if ((n & 1) == 1) {
  114.                 ans *= x;
  115.                 ans %= mod;
  116.                 n--;
  117.             } else {
  118.                 x *= x;
  119.                 x %= mod;
  120.                 n >>= 1;
  121.             }
  122.         }
  123.         return ans;
  124.     }
  125.  
  126.     public static long factorial(long n) {
  127.         long fact = 1L;
  128.         for (int i = 2; i <= n; i++) fact = (fact * i) % mod;
  129.         return fact;
  130.     }
  131.  
  132.     public static long firstDivisor(long n) {
  133.         if (n == 1 || n == 0) return n;
  134.         for (long i = 2; i * i <= n; i++)
  135.             if (n % i == 0) return i;
  136.         return -1;
  137.     }
  138.  
  139.     public static int ncr(int n, int r) {
  140.         // time O(n+r)
  141.         if (r > n)
  142.             return 0;
  143.         long[] inv = new long[r + 1];
  144.         inv[1] = 1;
  145.         // Getting the modular inversion
  146.         // for all the numbers
  147.         // from 2 to r with respect to m
  148.         for (int i = 2; i <= r; i++) {
  149.             inv[i] = mod - (mod / i) * inv[mod % i] % mod;
  150.         }
  151.         int ans = 1;
  152.         // for 1/(r!) part
  153.         for (int i = 2; i <= r; i++) {
  154.             ans = (int) (((ans % mod) * (inv[i] % mod)) % mod);
  155.         }
  156.         // for (n)*(n-1)*(n-2)*...*(n-r+1) part
  157.         for (int i = n; i >= (n - r + 1); i--) {
  158.             ans = (int) (((ans % mod) * (i % mod)) % mod);
  159.         }
  160.         return ans;
  161.     }
  162.  
  163.     public static long max3(long a, long b, long c) { return max2(max2(a, b), c);}
  164.  
  165.     public static long max2(long a, long b) {return Math.max(a, b);}
  166.  
  167.     public static long min3(long a, long b, long c) {return min2(min2(a, b), c);}
  168.  
  169.     public static long min2(long a, long b) { return Math.min(a, b); }
  170.  
  171.     public static int max3(int a, int b, int c) { return max2(max2(a, b), c); }
  172.  
  173.     public static int max2(int a, int b) { return Math.max(a, b); }
  174.  
  175.     public static int min3(int a, int b, int c) { return min2(min2(a, b), c); }
  176.  
  177.     public static int min2(int a, int b) {
  178.         return Math.min(a, b);
  179.     }
  180.  
  181.     /**************************************HELPER FUNCTION ENDS HERE ************************************/
  182.  
  183.     /*****************************************FAST INPUT STARTS HERE *************************************/
  184.  
  185.     public static void FIO(boolean isDebug){
  186.         sc = new Scanner();
  187.         out = new PrintWriter(new BufferedOutputStream(System.out));
  188.         if(isDebug){
  189.             try {
  190.                 debug = new PrintWriter(new FileOutputStream("debug.txt"));
  191.             }catch (IOException e){
  192.                 e.printStackTrace();
  193.             }
  194.         }
  195.  
  196.     }
  197.     public static void closeIO(){
  198.         sc.close();
  199.         out.flush();
  200.         out.close();
  201.         if(debug!=null){
  202.             debug.flush();
  203.             debug.close();
  204.         }
  205.     }
  206.  
  207.     private static class Scanner {
  208.         private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  209.         private StringTokenizer st = new StringTokenizer("");
  210.  
  211.         public String next() {
  212.             while (!st.hasMoreTokens())
  213.                 try {
  214.                     st = new StringTokenizer(br.readLine());
  215.                 } catch (IOException e) {
  216.                     e.printStackTrace();
  217.                 }
  218.             return st.nextToken();
  219.  
  220.         }
  221.  
  222.         public int nextInt() {
  223.             return Integer.parseInt(next());
  224.         }
  225.  
  226.         public long nextLong() {
  227.             return Long.parseLong(next());
  228.         }
  229.  
  230.         public double nextDouble() {
  231.             return Double.parseDouble(next());
  232.         }
  233.  
  234.         public int[] set_int_array(int n) {
  235.             int[] arr = new int[n];
  236.             for (int i = 0; i < n; i++) arr[i] = nextInt();
  237.             return arr;
  238.         }
  239.  
  240.         public long[] set_long_array(int n) {
  241.             long[] arr = new long[n];
  242.             for (int i = 0; i < n; i++) arr[i] = nextLong();
  243.             return arr;
  244.         }
  245.         public double[] set_double_array(int n){
  246.             double[] arr = new double[n];
  247.             for(int i =0;i<n;i++)arr[i] = sc.nextDouble();
  248.             return arr;
  249.         }
  250.  
  251.         public int[][] set_2D_int_array(int n) {
  252.             return set2DIntArray(n, n);
  253.         }
  254.  
  255.         public int[][] set2DIntArray(int row, int col) {
  256.             int[][] arr = new int[row][col];
  257.             for (int i = 0; i < row; i++)
  258.                 for (int j = 0; j < col; j++)
  259.                     arr[i][j] = nextInt();
  260.             return arr;
  261.         }
  262.  
  263.         public long[][] set_2D_long_array(int n) {
  264.             return set2DlongArray(n, n);
  265.         }
  266.  
  267.         public long[][] set2DlongArray(int row, int col) {
  268.             long[][] arr = new long[row][col];
  269.             for (int i = 0; i < row; i++)
  270.                 for (int j = 0; j < col; j++)
  271.                     arr[i][j] = nextLong();
  272.             return arr;
  273.         }
  274.  
  275.         public char[][] set_2D_char_array(int n) {
  276.             return set2DCharArray(n, n);
  277.         }
  278.  
  279.         public char[][] set2DCharArray(int row, int col) {
  280.             char[][] ch = new char[row][col];
  281.             for (int i = 0; i < row; i++)
  282.                 ch[i] = sc.next().toCharArray();
  283.             return ch;
  284.         }
  285.  
  286.         public void close() {
  287.             try {
  288.                 br.close();
  289.             } catch (IOException e) {
  290.                 e.printStackTrace();
  291.             }
  292.         }
  293.     }
  294.     /*****************************************FAST INPUT ENDS HERE *************************************/
  295. }
Success #stdin #stdout 0.09s 51236KB
comments (?)
stdin
copy 
123 321
stdout
copy 
171
https://ideone.com/sOghu7
language:
Java (HotSpot 12)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!