Given a Bucket having a capacity of N litres and the task is to determine that by how many ways you can fill it using two bottles of capacity of 1 Litre and 2 Litre only. Find the answer modulo 10^{8}.
Example 1:
Input:
3
Output:
3 
Explanation:
Let O denote filling by 1 litre bottle and
T denote filling by 2 litre bottle.
So for N = 3, we have :
{OOO,TO,OT}. Thus there are 3 total ways.
Example 2:
Input:
4
Output:
5 
Explanation:
Let O denote filling by 1 litre bottle and
T denote filling by 2 litre bottle.
So for N = 4, we have :
{TT,OOOO,TOO,OTO,OOT} thus there are 5 total ways.
Your Task:
You don't need to read input or print anything. Your task is to complete the function fillingBucket() which takes an Integer N as input and returns the number of total ways possible.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Combinatorics

Mathematics

Starter code: #User function Template for python3



class Solution:

    def fillingBucket(self, N):

        # code here

Solutions:
class Solution:

	def fillingBucket(self, N):
		a = 1
		b = 2
		if N <= 2:
			return N
		for i in range(3, N + 1):
			c = a + b % 10 ** 8
			a = b
			b = c
		return c % 10 ** 8


class Solution:

	def fillingBucket(self, N):
		mod = 100000000
		fib = [0] * (N + 2)
		fib[1] = 1
		fib[2] = 2
		for i in range(3, N + 1):
			fib[i] = fib[i - 1] % mod + fib[i - 2] % mod
		return fib[N] % mod


class Solution:

	def fillingBucket(self, N):
		if N == 1:
			return 1
		if N == 2:
			return 2
		dp = [0] * (N + 1)
		dp[1] = 1
		dp[2] = 2
		for i in range(3, len(dp)):
			dp[i] = (dp[i - 1] + dp[i - 2]) % 100000000
		return dp[-1]


class Solution:

	def fillingBucket(self, N):
		if N == 1 or N == 2:
			return N
		else:
			f = 1
			s = 2
			for i in range(3, N + 1):
				res = (f + s) % 10 ** 8
				f = s
				s = res
			return res


class Solution:

	def fillingBucket(self, n):
		if n == 1 or n == 2:
			return n
		dp = [0] * (n + 1)
		dp[0] = 1
		dp[1] = 2
		for i in range(2, n):
			dp[i] = (dp[i - 1] + dp[i - 2]) % 10 ** 8
		return dp[n - 1]


class Solution:

	def fillingBucket(self, N):
		if N == 1:
			return 1
		mod = int(100000000.0)
		dp = [0] * N
		dp[0] = 1
		dp[1] = 2
		for i in range(2, N):
			dp[i] = (dp[i - 1] + dp[i - 2]) % mod
		return dp[N - 1]


class Solution:

	def fillingBucket(self, N):
		dp = [0] * max(3, N + 1)
		dp[1] = 1
		dp[2] = 2
		for i in range(3, N + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % 10 ** 8
		return dp[N]


class Solution:

	def fillingBucket(self, N):
		dp = [0] * (N + 1)
		dp[0] = 1
		dp[1] = 1
		m = 100000000
		for i in range(2, N + 1):
			dp[i] = (dp[i - 1] % m + dp[i - 2] % m) % m
		return dp[N] % m


x = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
y = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

class Solution:

	def fillingBucket(self, n):
		global x, y
		self.x = x
		self.y = y
		if n <= len(self.x):
			return self.x[n - 1] % 100000000
		(i, j) = (self.y[-1], self.x[-1])
		k = 0
		n -= len(self.x)
		while k < n:
			t = i
			i = j
			j = t + i
			k += 1
			self.x.append(j)
			self.y.append(i)
		return j % 100000000


x = [1, 2, 3, 5, 8, 13]
y = [1, 1, 2, 3, 5, 8]

class Solution:

	def fillingBucket(self, n):
		global x, y
		self.x = x
		self.y = y
		if n <= len(self.x):
			return self.x[n - 1] % 100000000
		(i, j) = (self.y[-1], self.x[-1])
		k = 0
		n -= len(self.x)
		while k < n:
			t = i
			i = j
			j = t + i
			k += 1
			self.x.append(j)
			self.y.append(i)
		return j % 100000000


class Solution:

	def fillingBucket(self, N):
		k = 10 ** 8
		(x, y) = (1, 2)
		if N <= 2:
			return N
		for i in range(3, N + 1):
			c = (x + y) % k
			x = y
			y = c
		return c


class Solution:

	def fillingBucket(self, n):
		dp = [1, 2]
		for i in range(n - 2):
			dp.append((dp[-1] + dp[-2]) % 100000000)
		return dp[n - 1] % 100000000


class Solution:

	def fillingBucket(self, N):
		MOD = 10 ** 8
		(a, b) = (0, 1)
		res = 0
		for i in range(N):
			res = a + b
			res %= MOD
			(a, b) = (b, res)
		return res


class Solution:

	def fillingBucket(self, N):
		if N <= 2:
			return N
		a = 1
		b = 2
		c = 0
		for i in range(3, N + 1):
			c = (a + b) % 100000000
			a = b % 100000000
			b = c % 100000000
		return c


class Solution:

	def fillingBucket(self, N):
		return self.tabWoMem(N)

	def tabWoMem(self, N):
		if N <= 2:
			return N if N > 0 else 1
		prev2 = 1
		prev1 = 2
		for i in range(3, N + 1):
			temp = (prev1 + prev2) % 10 ** 8
			prev2 = prev1
			prev1 = temp
		return temp


from itertools import permutations

class Solution:

	def fillingBucket(self, N):
		if N < 3:
			return N
		A = [1, 2]
		for i in range(2, N):
			A.append((A[i - 1] + A[i - 2]) % 10 ** 8)
		return A[N - 1]


class Solution:

	def fillingBucket(self, N):
		a = [1, 1, 2, 3]
		if N <= 3:
			return a[N]
		for i in range(4, N + 1):
			a.append((a[i - 1] + a[i - 2]) % 100000000.0)
		return int(a[N])


class Solution:

	def fillingBucket(self, N):
		mod = pow(10, 8)
		dp = [0] * (N + 1)
		dp[0] = 1
		dp[1] = 1
		for i in range(2, N + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % mod
		return dp[N] % mod


class Solution:

	def fillingBucket(self, N):
		dp = [1] * (N + 1)
		for i in range(2, N + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % 10 ** 8
		return dp[-1] % 10 ** 8


class Solution:

	def fillingBucket(self, N):
		temp1 = 0
		temp2 = 1
		ans = 2
		if N == 1:
			return 1
		elif N == 2:
			return 2
		elif N == 3:
			return 3
		i = 0
		while i < N - 2:
			temp1 = temp2
			temp2 = ans
			ans = (temp1 + temp2) % 100000000
			i += 1
		return ans


class Solution:

	def fillingBucket(self, N):
		if N <= 2:
			return N
		(prevToPrev, prev) = (1, 2)
		for i in range(3, N + 1):
			current = (prev + prevToPrev) % 10 ** 8
			prevToPrev = prev
			prev = current
		return prev


class Solution:

	def fillingBucket(self, N):
		if N <= 2:
			return N
		dpArray = [0] * (N + 1)
		(dpArray[1], dpArray[2]) = (1, 2)
		for i in range(3, N + 1):
			dpArray[i] = (dpArray[i - 1] + dpArray[i - 2]) % 10 ** 8
		return dpArray[-1]


import math

class Solution:

	def fillingBucket(self, n):
		(a, b) = (1, 2)
		if n <= 2:
			return n
		for i in range(2, n):
			c = (a + b) % 10 ** 8
			a = b
			b = c
		return c


class Solution:

	def fillingBucket(self, N):
		dict = [0, 1, 2]
		for i in range(3, N + 1):
			dict.append((dict[i - 1] + dict[i - 2]) % 10 ** 8)
		return dict[N] % 10 ** 8


class Solution:

	def fillingBucket(self, N):
		mod = 10 ** 8
		if N == 1:
			return 1
		elif N == 0:
			return 0
		a = 1
		b = 2
		for i in range(3, N + 1):
			(a, b) = (b, (a + b) % mod)
		return b


class Solution:

	def fillingBucket(self, N):
		m = 10 ** 8
		prev = 1
		prev1 = 1
		for i in range(2, N + 1):
			curr = (prev % m + prev1 % m) % m
			prev1 = prev
			prev = curr
		return prev


class Solution:

	def fillingBucket(self, n):
		q = int(100000000.0)
		dp = [-1] * (n + 1)
		dp[0] = 1
		dp[1] = 1
		for i in range(2, n + 1):
			dp[i] = dp[i - 1] % q + dp[i - 2] % q
		return dp[n] % q


class Solution:
	MODULO = 10 ** 8

	def fillingBucket(self, N):
		if N == 1:
			return 1
		if N == 0:
			return 1
		(a, b) = (1, 2)
		for _ in range(N - 2):
			(b, a) = ((a + b) % self.MODULO, b)
		return b % self.MODULO


class Solution:

	def fillingBucket(self, N):
		fib = [0] * (N + 1)
		fib[0] = 1
		fib[1] = 1
		for i in range(2, N + 1):
			fib[i] = (fib[i - 1] + fib[i - 2]) % 10 ** 8
		return fib[N]


class Solution:

	def fillingBucket(self, N):
		(a, b) = (1, 2)
		if N == 1:
			return a
		elif N == 2:
			return b
		else:
			for i in range(3, N):
				(b, a) = (b + a, b)
				if b > 100000000:
					b = b % 100000000
			return (b + a) % 100000000


import sys
sys.setrecursionlimit(pow(10, 9))

class Solution:

	def fillingBucket(self, capacity):
		if capacity < 2:
			return 1
		dp = [-1 for i in range(capacity + 1)]
		mod = pow(10, 8)
		dp[0] = 1
		dp[1] = 1
		dp[2] = 2
		for i in range(3, capacity + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % mod
		return dp[capacity]


class Solution:

	def fillingBucket(self, N):
		a = 1
		b = 2
		mod = 100000000
		if N == 1:
			return a
		if N == 2:
			return b
		while N - 2 > 0:
			c = (a + b) % mod
			a = b
			b = c
			N = N - 1
		return b % mod


class Solution:

	def fillingBucket(self, N):
		if N <= 2:
			return N
		mod = 10 ** 8
		a = [1] * (N + 1)
		for n in range(2, N + 1):
			a[n] = (a[n - 1] + a[n - 2]) % mod
		return a[N]


class Solution:

	def fillingBucket(self, N):
		if N == 1:
			return 1
		if N == 2:
			return 2
		i = 3
		a = 1
		b = 2
		c = 0
		m = 10 ** 8
		while i <= N:
			c = (a + b) % m
			a = b % m
			b = c % m
			i += 1
		return c


class Solution:

	def fillingBucket(self, N):
		m = 10 ** 8
		comb = [0] * (N + 1)
		comb[0] = 1
		comb[1] = 1
		for i in range(2, N + 1):
			comb[i] = (comb[i - 1] % m + comb[i - 2] % m) % m
		return comb[N] % m


class Solution:

	def fillingBucket(self, N):
		MOD = 100000000
		prev = 0
		curr = 0
		nxt = 1
		while N > 0:
			N = N - 1
			curr = nxt
			nxt += prev
			nxt %= MOD
			prev = curr
		return nxt


class Solution:

	def fillingBucket(self, N):
		MOD = 100000000
		fib = [0] * (N + 1)
		(fib[0], fib[1]) = (1, 1)
		for i in range(2, N + 1):
			fib[i] = (fib[i - 1] + fib[i - 2]) % MOD
		return fib[N]


import sys
sys.setrecursionlimit(int(1000000.0))

class Solution:

	def fillingBucket(self, N):
		mod = int(100000000.0)
		if N < 3:
			return N
		dp = [-1] * (N + 1)
		dp[1] = 1
		dp[2] = 2
		for i in range(3, N + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % mod
		return dp[-1]


class Solution:

	def fillingBucket(self, N):
		(one, two) = (1, 1)
		for i in range(N - 1):
			(one, two) = ((one + two) % 10 ** 8, one)
		return one


class Solution:

	def fillingBucket(self, N):
		prev2 = 0
		prev1 = 1
		prev = 2
		if N == 0:
			return prev2
		if N == 1:
			return prev1
		if N == 2:
			return prev
		for i in range(3, N + 1):
			current = (prev1 + prev) % 100000000
			prev2 = prev1
			prev1 = prev
			prev = current
		return current


class Solution:

	def fillingBucket(self, N):
		l = [0 for i in range(N + 1)]
		l[-1] = 1
		l[-2] = 1
		a = 10 ** 8
		for i in range(N - 2, 0 - 1, -1):
			l[i] = (l[i + 1] + l[i + 2]) % a
		return l[0] % a


class Solution:

	def fillingBucket(self, N):
		if N == 1:
			return 1
		prev = 2
		scprev = 1
		for i in range(N - 2):
			temp = prev
			prev = (prev + scprev) % 100000000
			scprev = temp
		return prev


class Solution:

	def __init__(self):
		self.ans = 0

	def fillingBucket(self, N):
		dp = [0] * (N + 1)
		dp[N] = 1
		dp[N - 1] = 1
		for i in range(N - 2, -1, -1):
			dp[i] = (dp[i + 1] + dp[i + 2]) % 100000000
		return dp[0]


class Solution:

	def fillingBucket(self, N):
		(v1, v2, v3) = (1, 1, 0)
		for rec in bin(N + 1)[3:]:
			calc = v2 * v2
			(v1, v2, v3) = (v1 * v1 + calc, (v1 + v3) * v2, calc + v3 * v3)
			if rec == '1':
				(v1, v2, v3) = (v1 + v2, v1, v2)
		return v2 % 10 ** 8


class Solution:

	def fillingBucket(self, N):
		try:
			mod = 100000000
			d = [0] * (N + 1)
			d[0] = 0
			d[1] = 1
			d[2] = 2
			for i in range(3, N + 1):
				d[i] = (d[i - 1] + d[i - 2]) % mod
			return d[N]
		except:
			return d[N]