Question

Given an array of non zero ints find the number of steps taken to reach to given array, from an array of same length inited with 0

Answer 1

Answer:

Consider k = 4, n = 9  

Given array: 3 1 2 2 2 1 4 3 3  

i = 0

        3 _ _

temp[] has one element, 3 with count 1

i = 1

        3 1 _

temp[] has two elements, 3 and 1 with  

counts 1 and 1 respectively

i = 2

        3 1 2

temp[] has three elements, 3, 1 and 2 with

counts as 1, 1 and 1 respectively.

i = 3

        - - 2  

        3 1 2

temp[] has three elements, 3, 1 and 2 with

counts as 1, 1 and 2 respectively.

i = 4

        - - 2  

        - - 2  

        3 1 2

temp[] has three elements, 3, 1 and 2 with

counts as 1, 1 and 3 respectively.

i = 5

        - - 2  

        - 1 2  

        3 1 2

temp[] has three elements, 3, 1 and 2 with

counts as 1, 2 and 3 respectively.  

Now the question arises, what to do when temp[] is full and we see a new element – we remove the bottom row from stacks of elements, i.e., we decrease count of every element by 1 in temp[]. We ignore the current element.

i = 6

        - - 2  

        - 1 2  

temp[] has two elements, 1 and 2 with

counts as 1 and 2 respectively.

i = 7

          - 2  

        3 1 2  

temp[] has three elements, 3, 1 and 2 with

counts as 1, 1 and 2 respectively.

i = 8          

        3 - 2

        3 1 2  

temp[] has three elements, 3, 1 and 2 with

counts as 2, 1 and 2 respectively.

Explanation: