competitivecoder's blog

Simple question on bitmasking
By competitivecoder, 11 years ago, In English

Hello,I want to do this question which is tagged bitmasking.I am not getting how to solve this.Can anybody give me an approach how do I solve this ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
11 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Hello, you can observe that 1 <= n <= 1e9. This means that the number "n" has atmost 9 digits. Now let us assume that you need to generate all lucky numbers which have k digits. Now you can see that these k digits must comprise of either 4 or 7. So what you can do is just iterate each number from 0 to (2**k-1) and for each number check if current bit is 0/1. If the current bit is 0 it means 4 else it is 7. As an example let us take k = 2. So you have following cases :
00
01
10
11
Now mapping 0 with 4, 1 with 7, you can see that :
00 : 44
01 : 47
10 : 74
11 : 77
This means that you have generated all lucky numbers with digits : 2. Like this you can iterate k from 1 to 9, and generate the numbers. You can see my solution, it's easy to understand : http://codeforces.me/contest/535/submission/10713472

→ Reply