-
Notifications
You must be signed in to change notification settings - Fork 1k
/
Paint_Fence.py
68 lines (53 loc) · 1.45 KB
/
Paint_Fence.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
"""
___Paint Fence Algorithm___
Problem:
Given a fence with n posts and k colors
Find out the number of ways of painting the fence
such that at most 2 adjacent posts have the same color.
Input:
n : number of posts
k : number of colors
Output:
result: number of ways of painting
considering the condition above
"""
def paint_fence(n, k):
if n < 2 or k < (n/2) :
return -1 # n is not enough or k is not enough to obey the condition
total = [0]*(n-1)
same = [0]*(n-1)
diff = [0]*(n-1)
same[0] = k # We start from the case 2 (0 as i) till n (n-2 as i)
diff[0] = k*(k-1)
total[0] = k*k
for i in range(1, n-1):
same[i] = diff[i-1]
diff[i] = total[i-1]*(k-1)
total[i] = same[i]+diff[i]
return total[n-2]
if __name__ == "__main__":
post = int(input("Enter n, Number of Posts\n"))
color = int(input("Enter k, Number of Colors\n"))
result = paint_fence(post, color)
if result == -1 :
print("Painting is not possible following the condition")
else:
print("Number of Possiblities:", result)
# Sample Input/Output
# Enter n,Number of Posts
# 3
# Enter k,Number of Colors
# 5
# Number of Possiblities: 120
# Enter n,Number of Posts
# 10
# Enter k,Number of Colors
# 4
# Painting is not possible following the condition
# Enter n,Number of Posts
# 5
# Enter k,Number of Colors
# 3
# Number of Possiblities: 180
# Time Complexity O(n)
# Space Complexity O(n)