Блог пользователя cf_rk

Автор cf_rk, история, 5 лет назад, По-английски

You are given a binary string s (consisting of 0's and 1's). Count the number of substrings with count of 1's > count of 0's.

For eg. Input: 1010 Output: 3 Explanation: Possible substring with count of 1's > count of 0's are : {1} , {101} , {1}.

What I did? I converted all 0's to -1. Then the problem reduces to Count number of subarrays with positive sum. Then I used fenwick tree for it and it passed.

Is there any other approach for this. Thanks in advance!

  • Проголосовать: нравится
  • -21
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

Balanced BST

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -7 Проголосовать: не нравится

fft

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Find the number of intervals with sum 0. To do this, find the length of the intervals composed of only 0. The rest is trivial