Problem ZIGZAG

Abhinav Faujdar

Given an array, find the no. of zig-zag sub-sequences in it. A Zig-zag sequence has to be of odd length and if it starts with x, every odd positioned element needs to be x. Even positioned elements can be either x+1 or x-1.

Level: Easy

Explanation: We can use hashmap. We can store a pair of <value,state> in hashmap as key corresponding to last element of the sequence (and the count of all such sequences as the value for that key). State can be 0,-1 or 1. 0→ odd element , 1→ even element (x+1) , -1 → even element(x-1). Update hashmap while traversing array.

Complexity: O(NlogN)

Test case generation plan:

N=100000 for all cases (no. of elements of array)

test 0: all elements random ( hence what results is that answer=100000 since no sequence of 3-length arises)

test 1: chosen a value=41. A[i]=42 for all even i. Else randomly choose from 43(x+1) or 41(x-1)

test 2: A[i] is constant for all i (answer=N)

test 3: chosen randomly val=4683. (for i=1-20,000)A[i]=val. For(i=20,001 to 40,000)A[i]=val,val-1 or val+1 , randomly. For(i=40001 to 70,000)A[i]=10^9 or 10^9-1, randomly. For(i=70,001 to 100000)A[i] is randomly chosen.