Dada una string binaria, cuente el número de substrings que comienzan y terminan en 1. Por ejemplo, si la string de entrada es «00100101», entonces hay tres substrings «1001», «100101» y «101».
Fuente: experiencia de entrevista de Amazon | Set 162
Nivel de dificultad: Novato
Una solución simple es ejecutar dos bucles. Los bucles externos seleccionan cada 1 como punto de inicio y el bucle interno busca el final 1 y los incrementos cuentan cada vez que encuentran 1.
C++
// A simple C++ program to count number of
// substrings starting and ending with 1
#include<iostream>
using namespace std;
int countSubStr(char str[])
{
int res = 0; // Initialize result
// Pick a starting point
for (int i=0; str[i] !='\0'; i++)
{
if (str[i] == '1')
{
// Search for all possible ending point
for (int j=i+1; str[j] !='\0'; j++)
if (str[j] == '1')
res++;
}
}
return res;
}
// Driver program to test above function
int main()
{
char str[] = "00100101";
cout << countSubStr(str);
return 0;
}
Java
// A simple C++ program to count number of
//substrings starting and ending with 1
class CountSubString
{
int countSubStr(char str[],int n)
{
int res = 0; // Initialize result
// Pick a starting point
for (int i = 0; i<n; i++)
{
if (str[i] == '1')
{
// Search for all possible ending point
for (int j = i + 1; j< n; j++)
{
if (str[j] == '1')
res++;
}
}
}
return res;
}
// Driver program to test the above function
public static void main(String[] args)
{
CountSubString count = new CountSubString();
String string = "00100101";
char str[] = string.toCharArray();
int n = str.length;
System.out.println(count.countSubStr(str,n));
}
}
Python3
# A simple Python 3 program to count number of # substrings starting and ending with 1 def countSubStr(st, n) : # Initialize result res = 0 # Pick a starting point for i in range(0, n) : if (st[i] == '1') : # Search for all possible ending point for j in range(i+1, n) : if (st[j] == '1') : res = res + 1 return res # Driver program to test above function st = "00100101"; list(st) n= len(st) print(countSubStr(st, n), end="") # This code is contributed # by Nikita Tiwari.
C#
// A simple C# program to count number of
// substrings starting and ending with 1
using System;
class GFG
{
public virtual int countSubStr(char[] str,
int n)
{
int res = 0; // Initialize result
// Pick a starting point
for (int i = 0; i < n; i++)
{
if (str[i] == '1')
{
// Search for all possible
// ending point
for (int j = i + 1; j < n; j++)
{
if (str[j] == '1')
{
res++;
}
}
}
}
return res;
}
// Driver Code
public static void Main(string[] args)
{
GFG count = new GFG();
string s = "00100101";
char[] str = s.ToCharArray();
int n = str.Length;
Console.WriteLine(count.countSubStr(str,n));
}
}
// This code is contributed by Shrikant13
PHP
<?php
// A simple PHP program to count number of
// substrings starting and ending with 1
function countSubStr($str)
{
$res = 0; // Initialize result
// Pick a starting point
for ($i = 0; $i < strlen($str); $i++)
{
if ($str[$i] == '1')
{
// Search for all possible
// ending point
for ($j = $i + 1;
$j < strlen($str); $j++)
if ($str[$j] == '1')
$res++;
}
}
return $res;
}
// Driver Code
$str = "00100101";
echo countSubStr($str);
// This code is contributed by ita_c
?>
Javascript
<script>
// A simple javascript program to count number of
// substrings starting and ending with 1
function countSubStr(str,n)
{
let res = 0; // Initialize result
// Pick a starting point
for (let i = 0; i<n; i++)
{
if (str[i] == '1')
{
// Search for all possible ending point
for (let j = i + 1; j< n; j++)
{
if (str[j] == '1')
res++;
}
}
}
return res;
}
// Driver program to test the above function
let string = "00100101";
let n=string.length;
document.write(countSubStr(string,n));
// This code is contributed by rag2127
</script>
C++
// A O(n) C++ program to count number of
// substrings starting and ending with 1
#include<iostream>
using namespace std;
int countSubStr(char str[])
{
int m = 0; // Count of 1's in input string
// Traverse input string and count of 1's in it
for (int i=0; str[i] !='\0'; i++)
{
if (str[i] == '1')
m++;
}
// Return count of possible pairs among m 1's
return m*(m-1)/2;
}
// Driver program to test above function
int main()
{
char str[] = "00100101";
cout << countSubStr(str);
return 0;
}
Java
// A O(n) C++ program to count number of substrings
//starting and ending with 1
class CountSubString
{
int countSubStr(char str[], int n)
{
int m = 0; // Count of 1's in input string
// Traverse input string and count of 1's in it
for (int i = 0; i < n; i++)
{
if (str[i] == '1')
m++;
}
// Return count of possible pairs among m 1's
return m * (m - 1) / 2;
}
// Driver program to test the above function
public static void main(String[] args)
{
CountSubString count = new CountSubString();
String string = "00100101";
char str[] = string.toCharArray();
int n = str.length;
System.out.println(count.countSubStr(str, n));
}
}
Python3
# A Python3 program to count number of # substrings starting and ending with 1 def countSubStr(st, n) : # Count of 1's in input string m = 0 # Traverse input string and # count of 1's in it for i in range(0, n) : if (st[i] == '1') : m = m + 1 # Return count of possible # pairs among m 1's return m * (m - 1) // 2 # Driver program to test above function st = "00100101"; list(st) n= len(st) print(countSubStr(st, n), end="") # This code is contributed # by Nikita Tiwari.
C#
// A O(n) C# program to count
// number of substrings starting
// and ending with 1
using System;
class GFG
{
int countSubStr(char []str, int n)
{
int m = 0; // Count of 1's in
// input string
// Traverse input string and
// count of 1's in it
for (int i = 0; i < n; i++)
{
if (str[i] == '1')
m++;
}
// Return count of possible
// pairs among m 1's
return m * (m - 1) / 2;
}
// Driver Code
public static void Main(String[] args)
{
GFG count = new GFG();
String strings = "00100101";
char []str = strings.ToCharArray();
int n = str.Length;
Console.Write(count.countSubStr(str, n));
}
}
// This code is contributed by princiraj
PHP
<?php
// A simple PHP program to count number of
// substrings starting and ending with 1
function countSubStr($str)
{
$m = 0; // Initialize result
// Pick a starting point
for ($i = 0; $i < strlen($str); $i++)
{
if ($str[$i] == '1')
{
$m++;
}
}
// Return count of possible
// pairs among m 1's
return $m * ($m - 1) / 2;
}
// Driver Code
$str = "00100101";
echo countSubStr($str);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// A O(n) javascript program to count number of substrings
//starting and ending with 1
function countSubStr(str,n)
{
let m = 0; // Count of 1's in input string
// Traverse input string and count of 1's in it
for (let i = 0; i < n; i++)
{
if (str[i] == '1')
m++;
}
// Return count of possible pairs among m 1's
return m * Math.floor((m - 1) / 2);
}
// Driver program to test the above function
let str = "00100101";
let n = str.length;
document.write(countSubStr(str, n));
// This code is contributed by avanitrachhadiya2155
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA