ramlinuxprasad
BAN USERI think the question is meant to be multiples of the array element. For egs:
a = [2,4,6] // three caterpillars who eat at intervals of 2, 4 and 6
n = 10 // leaves
Hence the output in this case would be 4 leaves, since the 3rd, 5th, 7th and 9th leaf are not eaten by the three caterpillars.
import array
def count(n, a):
leaves = array.array('i', (0 for i in range(0, n)))
for i in a:
j = i - 1
while(j < n):
leaves[j] = 1
j += i
cnt = 0
for i in range(0, n):
if leaves[i] == 0:
cnt += 1
print " %d" % leaves[i],
if __name__ == '__main__':
count(10, [2, 4, 5])
This solution uses O(n) space and O(n) runtime complexity. I am not sure if there's a way to solve this using O(1) space complexity. If there is one I will be very interested to know the method.
- ramlinuxprasad September 09, 2014
I am not sure what's the question? Was the person asking for complexity analysis on what's the worst case for assignment statements? If that's the case the worst case would be O(n) operations since if you are given an array sorted with a decremented array elements then your assignment operation will take place for each element. However if he's looking for average case that would be almost O(1) amortized over a large data set. I am writing the code in java.
- ramlinuxprasad October 01, 2014