Compruebe si todos los 1 en una string binaria son equidistantes o no

Dada una string binaria str , la tarea es verificar si todos los 1 en la string son equidistantes o no. El término equidistante significa que la distancia entre cada dos 1 adyacentes es la misma. Tenga en cuenta que la string contiene al menos dos 1 .

Ejemplos:  

Entrada: str = “00111000” 
Salida: Sí 
La distancia entre todos los 1 es la misma y es igual a 1.

Entrada: str = “0101001” 
Salida: No 
La distancia entre el 1er ^y el 2do ¹ es 2 
y la distancia entre el 2do ^y el 3er ¹ es 3. 
 

Enfoque: almacene la posición de todos los 1 en la string en un vector y luego verifique si la diferencia entre cada dos posiciones consecutivas es la misma o no.

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
 
// Function that returns true if all the 1's
// in the binary string s are equidistant
bool check(string s, int l)
{
 
    // Initialize vector to store
    // the position of 1's
    vector<int> pos;
 
    for (int i = 0; i < l; i++) {
 
        // Store the positions of 1's
        if (s[i] == '1')
            pos.push_back(i);
    }
 
    // Size of the position vector
    int t = pos.size();
    for (int i = 1; i < t; i++) {
 
        // If condition isn't satisfied
        if ((pos[i] - pos[i - 1]) != (pos[1] - pos[0]))
            return false;
    }
 
    return true;
}
 
// Drivers code
int main()
{
    string s = "100010001000";
    int l = s.length();
    if (check(s, l))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function that returns true if all the 1's
// in the binary string s are equidistant
static boolean check(String s, int l)
{
 
    // Initialize vector to store
    // the position of 1's
    Vector<Integer> pos = new Vector<Integer>();
 
    for (int i = 0; i < l; i++)
    {
 
        // Store the positions of 1's
        if (s.charAt(i)== '1')
            pos.add(i);
    }
 
    // Size of the position vector
    int t = pos.size();
    for (int i = 1; i < t; i++)
    {
 
        // If condition isn't satisfied
        if ((pos.get(i) - pos.get(i-1)) != (pos.get(1) - pos.get(0)))
            return false;
    }
 
    return true;
}
 
// Drivers code
public static void main(String args[])
{
    String s = "100010001000";
    int l = s.length();
    if (check(s, l))
        System.out.print("Yes");
    else
        System.out.print("No");
}
}
 
// This code is contributed by Arnab Kundu

# Python3 implementation of the approach
 
# Function that returns true if all the 1's
# in the binary s are equidistant
def check(s, l):
 
    # Initialize vector to store
    # the position of 1's
    pos = []
 
    for i in range(l):
 
        # Store the positions of 1's
        if (s[i] == '1'):
            pos.append(i)
 
    # Size of the position vector
    t = len(pos)
    for i in range(1, t):
 
        # If condition isn't satisfied
        if ((pos[i] -
             pos[i - 1]) != (pos[1] -
                             pos[0])):
            return False
 
    return True
 
# Driver code
s = "100010001000"
l = len(s)
if (check(s, l)):
    print("Yes")
else:
    print("No")
 
# This code is contributed
# by mohit kumar

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function that returns true if all the 1's
// in the binary string s are equidistant
static bool check(String s, int l)
{
 
    // Initialize vector to store
    // the position of 1's
    List<int> pos = new List<int>();
 
    for (int i = 0; i < l; i++)
    {
 
        // Store the positions of 1's
        if (s[i]== '1')
        {
             
            pos.Add(i);
        }
    }
 
    // Size of the position vector
    int t = pos.Count;
    for (int i = 1; i < t; i++)
    {
 
        // If condition isn't satisfied
        if ((pos[i] - pos[i - 1]) != (pos[1] - pos[0]))
            return false;
    }
 
    return true;
}
 
// Drivers code
public static void Main(String []args)
{
    String s = "100010001000";
    int l = s.Length;
    if (check(s, l))
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
}
}
 
/* This code contributed by PrinciRaj1992 */

<script>
 
// Javascript implementation of the approach
 
// Function that returns true if all the 1's
// in the binary string s are equidistant
function check(s, l)
{
 
    // Initialize vector to store
    // the position of 1's
    var pos = [];
 
    for(var i = 0; i < l; i++)
    {
 
        // Store the positions of 1's
        if (s[i] == '1')
            pos.push(i);
    }
 
    // Size of the position vector
    var t = pos.length;
    for(var i = 1; i < t; i++)
    {
         
        // If condition isn't satisfied
        if ((pos[i] - pos[i - 1]) !=
            (pos[1] - pos[0]))
            return false;
    }
    return true;
}
 
// Drivers code
var s = "100010001000";
var l = s.length;
 
if (check(s, l))
    document.write( "Yes");
else
    document.write("No");
     
// This code is contributed by noob2000
 
</script>

Yes

Complejidad de tiempo: O(N) donde N es la longitud de la string.

Complejidad espacial : O(N) donde N es para el vector de posición extra