amh
BAN USERSolution in Python using DP O(n^2 k) solution.
#!/usr/bin/env python
A = [1,4,6,2,5,9]
n = len(A)
k = 3
T = [[0 for j in range(n)] for i in range(k)]
for x in range(n):
T[0][x] = 1
for i in range(1,k):
for j in range(n):
curr = A[j]
count = 0
for x in range(j):
if A[x] < A[j]:
count += T[i-1][x]
T[i][j] = count
count = sum(T[k-1])
print 'Total no. of ways:',count
The logic for my code is as follows: Given the condition that A[0] >= A[1] and A[n-1] <= A[1], it is guaranteed that a minima exists. This is because for a minima to not exist, the sequence has to be strictly decreasing but the special property negates it. So a transition from strictly decreasing to increasing/remain same has to happen somewhere. Even if there are multiple minimas, each minima is a transition. The following code just looks for a transition. This can be done in O(log n) time.
Python Code:
#!/usr/bin/env python
A = [9,7,7,2,1,3,7,5,4,7,3,3,4,8,6,9]
low = 0
high = len(A) - 1
found = False
trans = 0
while not found:
trans = (high + low)/2
if A[trans - 1] >= A[trans]:
low = trans
if A[trans] <= A[trans+1]:
high = trans
if high == low:
found = True
print 'Local minima', A[trans-1:trans+2]
The correct code
M = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[101,102,103,104],[500,600,700,800]]
m = len(M)
n = len(M[0])
ilow = 0
ihigh = m-1
jlow = 0
jhigh = n-1
irange = range(ilow,ihigh+1)
jrange = range(jlow,jhigh+1)
i = 0
j = 0
while ihigh > ilow or jhigh > jlow :
if i == ilow and j == jlow:
for x in jrange:
print M[i][x]
j = x
ilow +=1
i = ilow
irange.pop(0)
elif i == ilow and j == jhigh:
for x in irange:
print M[x][j]
i = x
jhigh -= 1
j = jhigh
jrange.pop()
elif i == ihigh and j == jhigh:
for x in reversed(jrange):
print M[i][x]
j = x
ihigh -= 1
i = ihigh
irange.pop()
elif i == ihigh and j == jlow:
ri = reversed(irange)
for x in ri:
print M[x][j]
i = x
jlow += 1
j = jlow
jrange.pop(0)
print M[ilow][jlow]
Python code:
#!/usr/bin/env python
#Write a program to print a 2-D array spirally- i.e, starting at a corner and spiraling inwards.
def plusminus(i,j,M):
m = len(M)
n = len(M[0])
print M[i][j]
while i < m-1 and j > 0 :
i += 1
j -= 1
print M[i][j]
return [i,j]
def minusplus(i,j,M):
m = len(M)
n = len(M[0])
print M[i][j]
while i> 0 and j < n-1:
i -= 1
j += 1
print M[i][j]
return [i,j]
M = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[100,101,102,104],[500,600,700,800]]
m = len(M)
n = len(M[0])
i = 0
j = 0
print M[i][j]
A = []
while (i < m-1 or j < n-1):
if i == m-1:
A = minusplus(i,j+1,M)
elif i == 0:
A = plusminus(i,j+1,M)
elif j == 0:
A = minusplus(i+1,j,M)
elif j == n-1:
A = plusminus(i+1,j,M)
i = A[0]
j = A[1]
Python Code: Assuming that ctrl+A , ctrl+C, ctrl+V over writes the original string.
output:
- amh September 20, 2011