So as the title says, given a binary string of length n (1<=n<=10^5) , find the number of unique decimals that can be obtained from subsequences of the binary string:

Example : 101

0=0

1=1

01 (same as 1) so rejected

10= 2

101= 5

11= 3

So, number of unique decimals are 5. I can only think of recursive solution.

How to approach this question ?

Btw it was asked today in Google hiring contest.

Suppose we are given number N we have to find a number M less than N such that M*M when divided by N gives maximum remainder . Also value of M should be maximum possible ( nearest to N).

It is given that all computed values are within integer range. for e.g : N=15

maximum remainder is obtained from M=5 and M=10

so M = 10 is the answer.

I could only formulate the naive solution for it which works in O(N) time complexity. Any better approach for this ??