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 - Convert Base 10 To Any Base - YouTube
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 