4

I'm trying to solve pretty complex problem with combinatorics and counting subsets. First of all let's say we have given set A = {1, 2, 3, ... N} where N <= 10^(18). Now we want to count subsets that don't have consecutive numbers in their representation.

Example

Let's say N = 3, and A = {1,2,3}. There are 2^3 total subsets but we don't want to count the subsets (1,2), (2,3) and (1,2,3). So in total for this question we want to answer 5 because we want to count only the remaining 5 subsets. Those subsets are (Empty subset), (1), (2), (3), (1,3). Also we want to print the result modulo 10^9 + 7.

What I've done so far

I was thinking that this should be solved using dynamical programming with two states (are we taking the i-th element or not), but then I saw that N could go up to 10^18, so I was thinking that this should be solved using mathematical formula. Can you please give me some hints where should I start to get the formula.

Thanks in advance.

someone12321
  • 755
  • 5
  • 24
  • Think Fibonacci numbers. – user58697 Jun 11 '17 at 16:01
  • You'll have to use Fibonacci sequence for this one - the formula is quite trivial: F(n+2) . You didn't mention what language you want the algorithm to be implemented in. – zwer Jun 11 '17 at 16:03

1 Answers1

3

Take a look at How many subsets contain no consecutive elements? on the Mathematics Stack Exchange.

They come to the conclusion that the number of non-consecutive subsets in the set {1,2,3...n} is the fib(n+2) where fib is the function computing the Fibonacci sequence for the number n+2. Your solution to n=3 conforms to this solution. If you can implement the Fibonacci algorithm, then you can solve this problem, but solving the question for a number as large as 10^18 will still be a challenge.

As mentioned in the comments here, you can check out the fast doubling algorithm on Hacker Earth.
It will find Fibonacci numbers in O(log n).

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
Jayson Boubin
  • 1,504
  • 2
  • 11
  • 19
  • 2
    Good explanation. +1 from me. You can use `fast doubling` method to calculate `n`th fibonacci term in `O(log n)` complexity. Check this [article](https://www.hackerearth.com/practice/notes/fast-doubling-method-to-find-nth-fibonacci-number/). – Sanket Makani Jun 11 '17 at 16:15
  • @SanketMakani Thanks for the info, that's a cool algorithm. I edited my post to include that. – Jayson Boubin Jun 11 '17 at 16:19