paramvi's blog

By paramvi, history, 4 months ago, In English,

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.

 
 
 
 
  • Vote: I like it  
  • -5
  • Vote: I do not like it  

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.