Initially, the zoo have a single chick. A chick gives birth to 2 chicks every day and the life expectancy of a chick is 6 days. Zoo officials want to buy food for chicks so they want to know the number of chicks on an N^{th} day. Help the officials with this task.
 
Example 1:
Input: N = 2 
Output: 3
Explanation: First day there is only 1 chick.
On second day total number of chicks = 3. 
Example 2:
Input: N = 3
Output: 9
Explanation: First day there is only 1 chick.
On second day total number of chicks = 3.
On third day total number of chicks = 9
 
Your Task:
You don't need to read or print anything, Your task is to complete the function NoOfChicks() which takes N as the input parameter and returns the total no. of chicks on the N^{th} day.
 
Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
 
Constraints:
1 <= N <= 35

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

	def NoOfChicks(self, N):

		# Code here

Solutions:
class Solution:

	def NoOfChicks(self, N):
		n = N
		dp = [0 for i in range(n + 1)]
		dp[1] = 1
		total = 1
		for i in range(2, n + 1):
			if i > 6:
				total = total - dp[i - 6]
			dp[i] = total * 2
			total = total * 3
		return total


class Solution:

	def NoOfChicks(self, N):
		l = [0 for i in range(N + 1)]
		l[1] = 1
		sum = l[1]
		for i in range(2, N + 1):
			if i > 6:
				sum -= l[i - 6]
			l[i] = sum * 2
			sum += l[i]
		return sum


class Solution:

	def NoOfChicks(self, N):
		lst = [1]
		for i in range(1, N):
			if i < 6:
				lst.append(sum(lst) * 2)
			else:
				lst.remove(lst[0])
				lst.append(sum(lst) * 2)
		return sum(lst)


class Solution:

	def NoOfChicks(self, N):
		arr = [0] * (N + 1)
		actual = [0] * (N + 1)
		arr[1] = 1
		actual[1] = 1
		for i in range(2, N + 1):
			curr = i - 6
			add = arr[i - 1]
			actual[i] = add * 2
			arr[i] = add * 2
			arr[i] += arr[i - 1]
			if curr >= 1:
				arr[i] -= 3 * actual[curr]
				actual[i] -= 2 * actual[curr]
		return arr[N]


class Solution:

	def NoOfChicks(self, N):
		live_chicks = 1
		dead_chicks = 0
		arr = [0] * 10 + [1]
		for i in range(N - 1):
			arr.append(live_chicks * 2)
			live_chicks += arr[-1] - arr[-6]
			dead_chicks += arr[-6]
		return live_chicks + arr[-6]


class Solution:

	def NoOfChicks(self, n):
		lst = [1]
		for i in range(1, n):
			if i < 6:
				lst.append(sum(lst) * 2)
			else:
				lst.pop(0)
				lst.append(sum(lst) * 2)
		return sum(lst)


class Solution:

	def NoOfChicks(self, n):
		li = list()
		li = [1] * (n + 1)
		if n == 1:
			return 1
		for i in range(2, n + 1):
			if i > 6:
				for j in range(i - 5, i):
					li[j] = li[j] - li[i - 6]
				li[i] = li[i - 1] * 3
			else:
				li[i] = li[i - 1] * 3
		return li[-1]


class Solution:

	def NoOfChicks(self, N):
		d = 1
		c = 1
		a = [1]
		i = -5
		while d < N:
			if i >= 0:
				c -= a[i]
			r = c * 2
			c = c + r
			a.append(r)
			i += 1
			d += 1
		return c


class Solution:

	def NoOfChicks(self, N):
		if N <= 1:
			return 1
		elif N <= 6:
			return 3 * self.NoOfChicks(N - 1)
		elif N == 7:
			return 3 * self.NoOfChicks(N - 1) - 3 * self.NoOfChicks(N - 6)
		else:
			return 3 * self.NoOfChicks(N - 1) - 2 * self.NoOfChicks(N - 6)


class Solution:

	def NoOfChicks(self, N):
		x = [1]
		for i in range(1, N):
			if i < 6:
				x.append(sum(x) * 2)
			else:
				x.pop(0)
				x.append(sum(x) * 2)
		return sum(x)


class Solution:

	def NoOfChicks(self, N):
		array = [1]
		total_chicks = 1
		for i in range(2, N + 1):
			if i > 6:
				dead = array.pop(0)
				total_chicks -= dead
			array.append(total_chicks * 2)
			total_chicks = total_chicks * 2 + total_chicks
		return total_chicks


class Solution:

	def NoOfChicks(self, n):
		if n <= 0:
			return 0
		c = [0] * (n + 1)
		d = [0] * (n + 1)
		if n >= 1:
			c[1] = 1
			d[1] = 1
		for i in range(2, n + 1):
			c[i] = c[i - 1] * 3
			d[i] = c[i - 1] * 2
			if i > 6:
				c[i] -= 3 * d[i - 6]
				d[i] -= 2 * d[i - 6]
		return c[n]


class Solution:

	def NoOfChicks(self, N):
		c = 1
		dp = [0] * N
		dp[0] = 1
		for i in range(1, N):
			if i >= 6:
				c -= dp[i - 6]
			dp[i] = c * 2
			c += dp[i]
		return c


class Solution:

	def NoOfChicks(self, N):
		n = N
		size = max(n, 7)
		dp = [0] * (size + 1)
		dp[0] = 0
		dp[1] = 1
		for i in range(2, 7):
			dp[i] = dp[i - 1] * 3
		dp[7] = 726
		for i in range(8, n + 1):
			dp[i] = (dp[i - 1] - 2 * dp[i - 6] // 3) * 3
		return dp[n]


class Solution:

	def NoOfChicks(self, N):
		lifespan = 6
		born = [1]
		alive = [1]
		died = [0]
		for i in range(1, N):
			if i < lifespan:
				numdied = 0
			else:
				numdied = born[i - lifespan]
			died += [numdied]
			born += [(alive[i - 1] - died[i]) * 2]
			alive += [alive[i - 1] + born[i] - died[i]]
		return alive[N - 1]


class Solution:

	def NoOfChicks(self, N):
		if N == 1:
			return 1
		temp = [0 for i in range(N)]
		temp[0] = 1
		count = 1
		for i in range(1, N):
			if i >= 6:
				count -= temp[i - 6]
			temp[i] = count * 2
			count += temp[i]
		return count


class Solution:

	def NoOfChicks(self, N):
		total_count = 1
		count_list = []
		for x in range(0, 45):
			count_list.append(0)
		count_list[6] = 1
		for x in range(1, N):
			total_count = total_count - count_list[x]
			count_list[x + 6] = total_count * 2
			total_count = total_count + total_count * 2
		return total_count


def nterm(n):
	if n == 1:
		return 1
	else:
		return int(2 / 3 * 3 ** (n - 1))

class Solution:

	def NoOfChicks(self, N):
		l = [1]
		for i in range(1, N):
			if i < 6:
				l.append(sum(l) * 2)
			else:
				l.remove(l[0])
				l.append(sum(l) * 2)
		return sum(l)


class Solution:

	def NoOfChicks(self, N):
		daily_chicks = [1]
		total_chicks = 1
		if N <= 0:
			return 0
		for i in range(1, N):
			if i >= 6:
				total_chicks -= daily_chicks[i - 6]
			daily_chicks.append(total_chicks * 2)
			total_chicks += total_chicks * 2
		return total_chicks


class Solution:

	def NoOfChicks(self, N):
		bornOn = [0, 1]
		totalOn = [0, 1]
		for i in range(2, N + 1):
			if i < 7:
				totalOn.append(totalOn[i - 1] * 3)
				bornOn.append(totalOn[i - 1] * 2)
			else:
				totalOn.append((totalOn[i - 1] - bornOn[i - 6]) * 3)
				bornOn.append((totalOn[i - 1] - bornOn[i - 6]) * 2)
		return totalOn[N]


class Solution:

	def NoOfChicks(self, N):
		act = [0 for i in range(N + 1)]
		act[1] = 1
		tot = [0 for i in range(N + 1)]
		tot[1] = 1
		for i in range(2, N + 1):
			if i >= 6:
				act[i] = 2 * (tot[i - 1] - act[i - 6])
				tot[i] = int(3 / 2 * act[i])
			else:
				act[i] = 2 * tot[i - 1]
				tot[i] = int(3 / 2 * act[i])
		return tot[N]


class Solution:

	def NoOfChicks(self, N):
		chicksAlive = 1
		buffer = [1]
		for n in range(1, N):
			if n < 6:
				buffer.append(2 * chicksAlive)
				chicksAlive = chicksAlive + 2 * chicksAlive
			else:
				chicksAlive = chicksAlive - buffer.pop(0)
				buffer.append(2 * chicksAlive)
				chicksAlive = chicksAlive + 2 * chicksAlive
		return chicksAlive


class Solution:

	def NoOfChicks(self, N):
		if N == 1:
			return 1
		res = [0] * N
		res[0] = 1
		chicks = 1
		for i in range(1, N):
			if i >= 6:
				chicks -= res[i - 6]
			res[i] = chicks * 2
			chicks += res[i]
		return chicks


class Solution:

	def NoOfChicks(self, N):
		a = [0 for i in range(N + 1)]
		(s, a[0]) = (1, 1)
		for i in range(1, N):
			if i - 6 >= 0:
				s -= a[i - 6]
			a[i] = 2 * s
			s += a[i]
		return s


class Solution:

	def NoOfChicks(self, N):
		arr = [None] * N
		arr[0] = 1
		c = 1
		for i in range(1, N):
			c = c - (arr[i - 6] if i >= 6 else 0)
			arr[i] = 2 * c
			c += arr[i]
		return c


class Solution:

	def NoOfChicks(self, N):
		arr = [[0, 1]]
		for i in range(1, N):
			old = sum(arr[-1])
			if i > 5:
				old -= arr[i - 6][1]
			new = old * 2
			arr.append([old, new])
		return sum(arr[-1])


class Solution:

	def NoOfChicks(self, N):
		day_counter = 1
		chicks = [1]
		while day_counter < N:
			if day_counter >= 6:
				chicks = chicks[1:]
			chicks.append(sum(chicks[0:day_counter]) * 2)
			day_counter += 1
		return sum(chicks)


class Solution:

	def NoOfChicks(self, N):
		dp = [0] * (N + 7)
		dp[6] = 1
		cnt = 1
		for i in range(1, N):
			cnt -= dp[i]
			dp[i + 6] = 2 * cnt
			cnt += 2 * cnt
		return cnt


total = {1: 1}
chicks = {1: 1}
for i in range(2, 36):
	if i > 6:
		chick = total[i - 1] - chicks[i - 6]
	else:
		chick = total[i - 1]
	total[i] = chick + chick * 2
	chicks[i] = chick * 2

class Solution:

	def NoOfChicks(self, N):
		return total[N]


class Solution:

	def NoOfChicks(self, N):
		l = max(7, N)
		x = [0] * (l + 1)
		x[1] = 1
		for i in range(2, 7):
			x[i] = x[i - 1] * 3
		x[7] = 726
		for i in range(8, N + 1):
			x[i] = (x[i - 1] - 2 * x[i - 6] // 3) * 3
		return x[N]


class Solution:

	def NoOfChicks(self, N):
		sol = [0] * N
		sol[0] = 1
		chick = 1
		for i in range(1, N):
			if i >= 6:
				chick -= sol[i - 6]
			sol[i] = chick << 1
			chick += sol[i]
		return chick


class Solution:

	def NoOfChicks(self, N):
		if N == 1:
			return 1
		a = [1] * (N + 1)
		d = 1
		for i in range(2, N + 1):
			if i <= 6:
				a[i] = 3 * a[i - 1]
			else:
				a[i] = 3 * (a[i - 1] - d)
				d = int(2 * a[i - 5] / 3)
		return a[N]


class Solution:

	def __init__(self):
		self.chicks = [0, 0, 0, 0, 0, 1]
		self.chicksTotal = 1
		self.start = True

	def getOlder(self):
		self.chicksTotal = self.chicksTotal - self.chicks[0]
		self.chicks.pop(0)
		if self.start:
			self.chicks.append(2)
			self.start = False
		else:
			self.chicks.append(sum(self.chicks[:5]) * 2)
		self.chicksTotal = self.chicksTotal + self.chicks[5]
		return

	def NoOfChicks(self, N):
		for i in range(N - 1):
			self.getOlder()
		return self.chicksTotal


from collections import deque

class Solution:

	def NoOfChicks(self, N):
		arr = deque()
		arr.append([0, 1])
		i = 1
		while N:
			if i < 6:
				arr.append([sum(arr[-1]), 0])
				arr[-1][1] += 2 * arr[-1][0]
			else:
				x = arr.popleft()
				arr.append([sum(arr[-1]) - x[1], 0])
				arr[-1][1] += 2 * arr[-1][0]
			N -= 1
			i += 1
		return sum(arr[-2])


class Solution:

	def NoOfChicks(self, N):
		n = N
		arr = [1]
		for i in range(5):
			arr.append(sum(arr) * 2)
		if n <= 6:
			return sum(arr[:n])
		index = 7
		while index < N + 1:
			arr.append((sum(arr) - sum(arr[:index - 6])) * 2)
			index += 1
		return sum(arr) - sum(arr[:index - 7])


class Solution:

	def NoOfChicks(self, N):
		deaths = [1]
		chicks = 1
		for i in range(N - 1):
			if i - 5 >= 0:
				chicks -= deaths[i - 5]
			deaths.append(chicks * 2)
			chicks *= 3
		return chicks


class Solution:

	def NoOfChicks(self, N):
		newborn = [1, 0, 0, 0, 0, 0]
		total = 1
		for i in range(N - 1):
			total -= newborn[-1]
			newborn.pop()
			newborn.insert(0, total * 2)
			total *= 3
		return total


class Solution:

	def NoOfChicks(self, N):
		a = [0] * 35
		for i in range(0, 35):
			if i < 6:
				a[i] = 3 ** i
			elif i == 6:
				a[i] = 726
			else:
				a[i] = 3 * (a[i - 1] - a[i - 6] * 2 // 3)
		return a[N - 1]
		return a


class Solution:

	def NoOfChicks(self, N):
		(arr, k) = ([1], 1)
		for i in range(1, N):
			if i >= 6:
				k -= arr[i - 6]
			arr.append(k * 2)
			k += arr[i]
		return k


class Solution:

	def NoOfChicks(self, n):
		dp = [0] * (n + 1)
		dp[1] = a = 1
		for i in range(2, n + 1):
			dp[i] = 2 * a - (2 * dp[i - 6] if i >= 6 else 0)
			a += dp[i]
			a -= dp[i - 6] if i >= 6 else 0
		return a


class Solution:

	def NoOfChicks(self, N):
		c = 1
		l = []
		l.append(c)
		for i in range(1, 6):
			c = c * 3
			l.append(c)
		l.append(726)
		for i in range(7, N):
			l.append((l[i - 1] - 2 * l[i - 6] // 3) * 3)
		ans = l[N - 1]
		return ans


class Solution:

	def NoOfChicks(self, N):
		cl = []
		dead = 0
		cl.append(1)
		if N == 1:
			return 1
		for i in range(1, N, 1):
			if i >= 6:
				cl[i - 6] = 0
				cl.append(2 * sum(cl[:i]))
			else:
				cl.append(3 * cl[i - 1])
		return cl[N - 1]


class Solution:

	def NoOfChicks(self, N):
		chick = [1]
		if N == 1:
			return chick[0]
		else:
			for _ in range(1, N):
				if _ < 6:
					chick.append(chick[-1] + chick[-1] * 2)
				elif _ >= 6:
					for i in range(1, len(chick)):
						chick[i] = chick[i] - chick[0]
					del chick[0]
					chick.append(chick[-1] + chick[-1] * 2)
			return chick[-1]


class Solution:

	def NoOfChicks(self, n):
		l = [0] * (n + 1)
		l[1] = 1
		if n == 1:
			return 1
		for i in range(2, n + 1):
			if i > 6:
				if i != 7:
					l[i] = 3 * (l[i - 1] - l[i - 6] * 2 // 3)
				else:
					l[i] = 3 * (l[i - 1] - 1)
			else:
				l[i] = 3 * l[i - 1]
		return l[i]


class Solution:

	def NoOfChicks(self, n):
		arr1 = [1]
		for i in range(1, n):
			if i < 6:
				arr1.append(sum(arr1) * 2)
			else:
				arr1.remove(arr1[0])
				arr1.append(sum(arr1) * 2)
		return sum(arr1)


class Solution:

	def NoOfChicks(self, N):
		newChicks = [0] * (N + 1)
		totalChicks = [0] * (N + 1)
		expiredChicks = [0] * (N + 1)
		newChicks[1] = 1
		totalChicks[1] = 1
		for i in range(2, len(totalChicks)):
			expiredChicks = newChicks[i - 6] if i > 6 else 0
			aliveToday = totalChicks[i - 1] - expiredChicks
			newChicks[i] = aliveToday * 2
			totalChicks[i] = aliveToday + newChicks[i]
		return totalChicks[-1]


class Solution:

	def NoOfChicks(self, N):
		startingChicks = 1
		totalCount = startingChicks
		lifeDays = 6
		chickList = [startingChicks]
		for day in range(1, N):
			if len(chickList) == lifeDays:
				totalCount -= chickList.pop(0)
			chickList.append(totalCount * 2)
			totalCount += chickList[len(chickList) - 1]
		return totalCount