There were total 6 questions to be done in 4 hours.

Question 1: Love Nines

Given a number N, find out minimum number of numbers needed whose last digit is 9 to make sum N. Output -1 if not possible.

Examples:
209 => Output: 1 (209's last digit is 9)
37 => Output: 3 (19 + 9 + 9)

Solution

Question 2: BIT Land

Given a string S of length N containing only 0-9, you have to make all the frequency of digits even by removing digits from the number S. Remove in a way such that the difference between the index of first and last digit removed is minimum and length of the resulting string is maximum. Output -1 if removal of digits is not required or it is not possible to get a resulting string.

Examples:
0001112233 => 1 (Remove 0 of index 2 and 1 of index 3)

Solution

Question 3: TAKER Tree

Lets define a taker tree of size N + 1 as a tree whose nodes are from 0 to N and parent of node X is obtained by removing the last set bit of X. Given N find the length of the longest path existing between any 2 nodes.

Constraints:
1 <= T <= 100,000
1 <= N <= 1,000,000,000

Example Tree:

    0
 /	| \
2	1  4
|
3

Question 4: Too Much Difference

Given an array A of length N and a number K. For each element A[i] in A you can apply the following operations any number of times:

• if A[i] is divisible by K, divide A[i] by K
• if A[i] is not divisible by K, multiply A[i] by K

Find minimum difference possible between the maximum and minimum number after applying those operations any number of times.

Constraints:
1 <= N <= 10,000
2 <= K <= 100

Examples:
A = [87 86 82 49 9] and K = 5 => 42 [Multiply 9 (A[4]) by 5]

Solution

Question 5:

Online queries:
Type 1. Change value of index x to v
Type 2. Sum of all values with index less than or equal to x

Constraints:
Q <= 100,000
x <= 10^18

Question 6: Shady Strings

Given a string S find the largest product possible of length of two non-overlapping palindrome substrings of odd length of S.

Constraints:
1 <= |S| <= 10000

Examples:
ababbb => 9 (aba and bbb)