Број подстрингова који почињу и завршавају са 1 - Решење

Анализа свих сегмената

Број свих сегмената који почињу и завршавају са 1 можемо једноставно одредити анализирајући све сегменте. У спољашњој петљи анализирамо један по један карактер. Свакy јединицу на коју наиђемо (за свако \(i\) такво да је \(s_i\) једнако 1), разматрамо као почетак сегмента и у унутрашњој петљи (бројачем \(j\) од \(i+1\) до краја стринга) тражимо јединицу којом се сегмент завршава. За сваку јединицу пронађену у унутрашњој петљи (за свако \(j\) такво да је \(s_j\) једнако 1) увећавамо број сегмената.

#include <iostream>
#include <string>

using namespace std;

int broj1x1Podstringova(const string& s) {
  int n = s.length();
  int br = 0;
  for (int i = 0; i < n - 1; i++)
    if (s[i] == '1')
      for (int j = i + 1; j < n; j++)
        if (s[j] == '1')
          br++;
  return br;
}

int main() {
  string s;
  cin >> s;
  cout << broj1x1Podstringova(s) << endl;
  return 0;
}

Бројање јединица

Сваки сегмент који почиње и који се заврашава јединицом дефинисан је позицијама две јединице у стрингу, па је укупан број тражених сегмената једнак броју начина да се изаберу две различите јединице у стрингу. Ако је укупан број јединица у стрингу \(b\) онда две јединице можемо изабрати на \(\frac {b \cdot (b - 1)}{2}\) начина.

#include <iostream>
#include <string>

using namespace std;

int broj1x1Podstringova(const string& s) {
  int brojJedinica = 0;
  for (char c : s)
    if (c == '1')
       brojJedinica++;
  return brojJedinica * (brojJedinica - 1) / 2;
}

int main() {
  string s;
  cin >> s;
  cout << broj1x1Podstringova(s) << endl;
  return 0;
}