paramvi's blog

By paramvi, history, 10 days 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  

»
10 days 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).

»
10 days 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.