Блог пользователя paramvi

Автор paramvi, история, 7 месяцев назад, По-английски,

Hi, so this problem was asked in one of the job hiring contest which is over now. So the problem is as follows:

Cool numbers are defined as numbers having digits only 2 and 5. So example of cool digits are 2, 5, 22, 25, 225, while 12, 23, 221 are not cool numbers because all their digits are not from {2, 5}. Let f(k) be defined as the function having value as a cool number greater than or equal to k. For a given pair of { L, R }, I need to evaluate ( f(L)+f(L+1)+....+f(R) ). Constraints of L, R {1<=L<=R<=10^9}

How can I solve the above problem. Any hint or approach is appreciated.

 
 
 
 
  • Проголосовать: нравится  
  • -5
  • Проголосовать: не нравится  

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by paramvi (previous revision, new revision, compare).

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

An efficient way to compute would be digit dp, but given the constraints, brute force would do perfectly fine as there are O(3^8) lucky numbers in the range.