ZIO Question 4-12 Editorial(Unofficial)

Hey there,
‘Editorials for ZIO exam’ Question 1 would be added soon

Question 2. We are given a list of number. We have to flip the signs of some of the elements such that in prefix sum array, no element is negative. We have to minimise the number of flips.

Quick Explanation. We can maintain a prefix sum array, and whenever we counter a -ve sign, we can the flip the sign of the smallest number obtained so far.

Case 1 : [3, -2, 3, -1, -2, -2, -4]
Solution : We get prefix sum array as [3, 1, 4, 3, 1, -1, -5]
As we can see that first negative element of the prefix sum array is at index 5 and at/before index 5, -2 is the smallest number. Thus we negate any of the -2 present before index 5

Consider negating -2 at index 1, we get prefix sum array as [3, 5, 8, 7, 5, 3, -1] Now we get the last element of prefix sum array negative so we can negate smallest number obtained at/before index 6

All Elements of prefix sum array are positive in 2 steps.

Case 2 : a = [-15, -12, -10, -13, -2, -3, -17, -19, -5, -9]
Solution : Prefix sum array - [-15, -27, -37, -50, -52, -55, -72, -91, -96, -105]
We’ll move in similar way as before, we get prefix sum array as
[15, 3, -7, …] negated a[0]
[15, 27, 17, 4, 2, -1, …] negated a[1]
[15, 27, 17, 30, 28, 25, 8, -11, …] negated a[4] as it was smallest on/before index 5
[15, 27, 17, 30, 28, 25, 8, 27, 22, 13] negated a[7]

Obtained prefix sum with all positive elements in 4 steps

Case 3 : a = [-12, -2, -16, -19, -9, -3, -7, -11, -17, -3, -15, -10, -10, -15, -8]
Prefix array - [-12, -14, -30, -49, -58, 61, -68, -79, -96, -99, -114, -124, -134, -149, -157]
Again,
[12, 10, -6, …] negating a[0]
[12, 10, 26, 7, -2, …] negating a[2]
[12, 10, 26, 45, 36, 33, 26, 15, -2, …] negating a[3]
[12, 10, 26, 45, 36, 33, 26, 15, 32, 29, 14, 4, -6, …] negating a[8]
[12, 10, 26, 45, 36, 33, 26, 15, 32, 29, 44, 34, 24, 9, 1] negating a[10]

Answer -> 5 steps

Question 3. Convert a regular integer into solid integer(that doesn’t use digit ‘0’)
Quick Explanation - Convert given base 10 integer to base 9 integer
How to convert base 10 to base 9 - We repeatedly divide the number by 9 until the result is equal to 0 and obtain the remainder for each division operation. writing all the remainders together in reverse order will give the result

Explanatory Video - https://www.youtube.com/watch?v=rVU-H522Dvc

Case 1: n = 100
100 / 9 = 11, 100 %(modulo) 9 = 1
11 / 9 = 1, 11 % 9 = 2
1 / 9 = 0, 1 % 9 = 1

Remainders = 1,2,1
Remainders in reverse order = 121 = Answer

Case 2: n = 2000
2000 / 9 = 222, 2000 % 9 = 2
222 / 9 = 24, 222 % 9 = 6
24 / 9 = 2, 24 % 9 = 6
2 / 9 = 0, 2 % 9 = 2
Remainders in reverse order = 2662 = Answer

Case 3: n = 100000
100000 / 9 = 11111, 100000 % 9 = 1
11111 / 9 = 1234, 11111 % 9 = 5
1234 / 9 = 137, 1234 % 9 = 1
137 / 9 = 15, 137 % 9 = 5
15 / 9 = 1, 15 % 9 = 6
1 / 9 = 0, 1 % 9 = 1
Remainders in reverse order - 162151 = Answer

Question 4. Given x, y, k, Convert x to y where operations allowed are -
x -= 1 Subtract 1 from x
x *= k Multiply x by k

For case 1 we can try all possible operations in level order manner.
And for rest of the cases greedy works, i.e, if moving in reverse function (y -> x) operations allowed y += 1, y /= k(if y is divisible), we can get the result

Case 1. covert(3, 10, 2)
Brute force goes like .

			  3
		2			6
	1		4	  5		    12
   0 2     3 8   4 (10)    11  24

10 result obtained with min 3 operations, i.e 3 -> 6 -> 5 -> 10

Case 2. covert(4, 92, 3)
Moving in greedy way will give us the answer(soon share the proof :))
Thus whenever y is divisible by k = 3 we divide it else add 1 to it(as we are moving from y -> x)
92 -> 93 -> 31 -> 32 -> 33 -> 11 -> 12 -> 4

Involves 7 operations

Case 3. convert(11, 104250, 2)
Again using greedy approach
104250 -> 52125 -> 52126 -> 26063 -> 26064 -> 13032 -> 6516 -> 3258 -> 1629 -> 1630 -> 815 -> 816 -> 413 -> 414 -> 212 -> 106 -> 52 -> 54 -> 27 -> 28 -> 14 -> 7 -> 8 -> 9 -> 10 -> 11.

Involves 24 operations.

Feel free to ask anything or to report any mistake :slight_smile:

3 Likes