elite_c0der's blog

Question from Google Online Test
By elite_c0der, history, 3 years ago, In English

Recently I have given the Google Online Test. There were 2 questions that are to be done in 1 hr. Even after the contest I am not able to solve the question and now I need help for this question.

Problem

You are given a string S of length n. The string S consists of characters 0's and 1's only. For each subsequence for string s, you need to find decimal representation and display the number of distinct decimal values of the subsequences. display answer%1000000007. 1<=T<=10 1<=n<=10^5 eg 1 3 110 output- 5 Any help will be appreciated. Thanks....

  • Vote: I like it
  • +38
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 5   Vote: I like it +19 Vote: I do not like it

I have an approach for this problem.

Let total denotes, total number of distinct numbers possible.

Let one denotes, number of numbers in total in which if we append 1 at the end then the number will already be present in the total set.

Let zero denotes, number of numbers in total in which if we append 0 at the end then the number will already be present in the total set.

So, let's say we are at character i and 

int newNumbers;
if(i == '1'):
    newNumbers = total + (total - one);
    one += (total - one);
    
else 
    newNumbers = total + (total - zero);
    zero += (total - zero);
total = newNumbers;

Think it like this Like If my total set contains 0, 1, 10. Then if the current character is 0 then the possible new numbers are 0, 10, 100 and two of these three numbers were already present in my set, so I have to remove them.

Code

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks a lot!

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Then if the current character is 1 then the possible new numbers are 0, 10, 100 and two of these three numbers were already present in my set, so I have to remove them.

    I think the current character should be 0.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u pls refer what technique/method/algo is this? I didn't got this wholly, so want to read on this.

    Firstly I thought doing this will stuck in infinite loop, but now this seems magical !!

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

another approach would be to remove prefix consecutive zeros , come at first index lets call it idx such $$$ s[idx]$$$ == '1' , now apply total number of distinct sequence algorithm which is classic DP question for the string $$$ s[idx+1:] $$$, that will be your answer, also you have to add one if there is zero in the string.

reasoning behind this is basically, after you get '1', whatever you append multiplies prefix by 2 and current number in it, and it suffice for the distinct decimal condition. in other words every distinct subsequence has unique decimal representation.

→ Reply
»
3 years ago, # |
← Rev. 7   Vote: I like it -9 Vote: I do not like it

Deleted

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Does Anyone Knows similar problem like this on codeforces ?? it will be highly appreciated !!

→ Reply