DIVISION - Divisiblity by 3
Divisiblity by 3 rule is pretty simple rule: Given a number sum the digits of number and check if sum is divisible by 3.If divisible then it is divisible by 3 else not divisible.Seems pretty simple but what if we want to extend this rule in binary representation!!
Given a binary representation we can again find if it is divisible by 3 or not. Making it little bit interesting what if only length of binary representation of a number is given say n.
Now can we find how many numbers exist in decimal form (base 10) such that when converted into binary (base 2) form has n length and is divisible by 3 ?? (1 <= n < 2*10^18)
Input
Length of binary form: n
Output
Print in new line the answer modulo 1000000007.
Example
Input
1 2
Output
1 2
Explanation: For n=2 there are only 2 numbers divisible by 3 viz.0 (00) and 3 (11) and having length 2 in binary form.
NOTE: There are multiple testfiles containing many testcases each so read till EOF.
Warnings: Leading zeros are allowed in binary representation and slower languages might require fast i/o. Take care.
hide comments
|
klu_70163:
2019-02-11 08:16:17
what is the code |
|
nadstratosfer:
2018-04-01 07:22:29
AC in Python depends more on luck than anything else. If TLE, resubmit another 10 times, perhaps you'll get lucky. TL carefully set to prevent us passing with a for loop counting numbers up to 2^(10^18). </sarcasm>
|
|
vish_14:
2017-08-17 03:21:53
TLE in python cost me 4 submission.
|
|
candide:
2017-04-21 19:13:44
Good problem to play with C optimisations. AC in Python. Nevertheless, description could be better, even the title contains a typo. The sentence "numbers in decimal form(base 10) such that when converted into binary(base 2) ..." is misleading and meaningless: does my age change if written in binary vs decimal ? Definition of the lenght of a binary representation is unexpected as it allows for instance 100101 to have length 42 instead of 6. Input format is unclear. Last edit: 2017-04-21 21:23:45 |
|
mkfeuhrer:
2016-06-17 11:57:43
good problem !! had to thnk a lot.... basically see for few starting cases .....ull get the answer!! use modular exponention :-) |
|
Piyush Kumar:
2016-06-16 16:58:07
The time limit is unnecessarily strict! |
|
prakash_reddy:
2016-01-17 20:04:40
very easy if u know modular exponentiation...... |
|
Thotsaphon Thanatipanonda:
2015-10-03 16:26:40
Finally I can solve this problem using Java with I/O optimization and reduce number of modulo. :D |
|
Rahul yadav:
2015-09-18 15:22:48
nice question
|
|
Parul Yadav:
2015-09-05 18:26:08
use scanf/printf |
| Added by: | Bhavik |
| Date: | 2014-06-28 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | own |
RSS