Найдите все двоичные последовательности четной длины с одинаковой суммой первой и второй половины битов

Опубликовано: 20 Января, 2022

Учитывая число n, найдите все двоичные последовательности длины 2n, такие, что сумма первых n битов равна сумме последних n битов.
Примеры:

 Ввод: N = 2
Выход:
0101 1111 1001 0110 0000 1010 

Ввод: N = 3
Выход: 
011011 001001 011101 010001 101011 111111
110011 101101 100001 110101 001010 011110 
010010 001100 000000 010100 101110 100010 
110110 100100

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Идея состоит в том, чтобы исправить первый и последний бит, а затем повторить оставшиеся 2 * (n-1) бит. Когда мы исправляем первый и последний бит, есть четыре возможности:

  1. Первый и последний биты равны 1, оставшиеся n - 1 бит с обеих сторон также должны иметь одинаковую сумму.
  2. Первый и последний биты равны 0, оставшиеся n - 1 бит с обеих сторон также должны иметь одинаковую сумму.
  3. Первый бит равен 1, а последний бит равен 0, сумма оставшихся n - 1 бит на левой стороне должна быть на 1 меньше суммы n-1 бит на правой стороне.
  4. Первый бит равен 0, а последний бит равен 1, сумма оставшихся n - 1 бит на левой стороне должна быть на 1 больше, чем сумма n - 1 бит на правой стороне.

Below is implementation of above idea –
 

C++

// C++ program to print even length binary sequences
// whose sum of first and second half bits is same
#include <bits/stdc++.h>
using namespace std;
 
// Function to print even length binary sequences
// whose sum of first and second half bits is same
 
// diff --> difference between sums of first n bits
// and last n bits
// out --> output array
// start --> starting index
// end --> ending index
void findAllSequences(int diff, char* out, int start, int end)
{
    // We can"t cover difference of more than n with 2n bits
    if (abs(diff) > (end - start + 1) / 2)
        return;
 
    // if all bits are filled
    if (start > end)
    {
        // if sum of first n bits and last n bits are same
        if (diff == 0)
            cout << out << " ";
        return;
    }
 
    // fill first bit as 0 and last bit as 1
    out[start] = "0", out[end] = "1";
    findAllSequences(diff + 1, out, start + 1, end - 1);
 
    // fill first and last bits as 1
    out[start] = out[end] = "1";
    findAllSequences(diff, out, start + 1, end - 1);
 
    // fill first and last bits as 0
    out[start] = out[end] = "0";
    findAllSequences(diff, out, start + 1, end - 1);
 
    // fill first bit as 1 and last bit as 0
    out[start] = "1", out[end] = "0";
    findAllSequences(diff - 1, out, start + 1, end - 1);
}
 
// Driver program
int main()
{
    // input number
    int n = 2;
 
    // allocate string containing 2*n characters
    char out[2 * n + 1];
 
    // null terminate output array
    out[2 * n] = "";
 
    findAllSequences(0, out, 0, 2*n - 1);
 
    return 0;
}

Java

// Java program to print even length binary
// sequences whose sum of first and second
// half bits is same
import java.io.*;
import java.util.*;
 
class GFG
{
    // Function to print even length binary sequences
    // whose sum of first and second half bits is same
  
    // diff --> difference between sums of first n bits
    // and last n bits
    // out --> output array
    // start --> starting index
    // end --> ending index
    static void findAllSequences(int diff, char out[],
                                     int start, int end)
    {
        // We can"t cover difference of more
        // than n with 2n bits
        if (Math.abs(diff) > (end - start + 1) / 2)
            return;
  
        // if all bits are filled
        if (start > end)
        {
            // if sum of first n bits and
            // last n bits are same
            if (diff == 0)
            {
                System.out.print(out);
                System.out.print(" ");
            }   
            return;
        }
  
        // fill first bit as 0 and last bit as 1
        out[start] = "0";
        out[end] = "1";
        findAllSequences(diff + 1, out, start + 1, end - 1);
  
        // fill first and last bits as 1
        out[start] = out[end] = "1";
        findAllSequences(diff, out, start + 1, end - 1);
  
        // fill first and last bits as 0
        out[start] = out[end] = "0";
        findAllSequences(diff, out, start + 1, end - 1);
  
        // fill first bit as 1 and last bit as 0
        out[start] = "1";
        out[end] = "0";
        findAllSequences(diff - 1, out, start + 1, end - 1);
    }
     
    // Driver program
    public static void main (String[] args)
    {
        // input number
        int n = 2;
  
        // allocate string containing 2*n characters
        char[] out = new char[2 * n + 1];
  
        // null terminate output array
        out[2 * n] = "";
  
        findAllSequences(0, out, 0, 2*n - 1);
    }
}
 
// This code is contributed by Pramod Kumar

Python3

# Python3 program to print even length binary sequences
# whose sum of first and second half bits is same
 
# Function to print even length binary sequences
# whose sum of first and second half bits is same
 
# diff --> difference between sums of first n bits
# and last n bits
# out --> output array
# start --> starting index
# end --> ending index
def findAllSequences(diff, out, start, end):
 
    # We can"t cover difference of more than n with 2n bits
    if (abs(diff) > (end - start + 1) // 2):
        return;
 
    # if all bits are filled
    if (start > end):
        # if sum of first n bits and last n bits are same
        if (diff == 0):
            print("".join(list(out)),end=" ");
        return;
 
    # fill first bit as 0 and last bit as 1
    out[start] = "0";
    out[end] = "1";
    findAllSequences(diff + 1, out, start + 1, end - 1);
 
    # fill first and last bits as 1
    out[start] = out[end] = "1";
    findAllSequences(diff, out, start + 1, end - 1);
 
    # fill first and last bits as 0
    out[start] = out[end] = "0";
    findAllSequences(diff, out, start + 1, end - 1);
 
    # fill first bit as 1 and last bit as 0
    out[start] = "1";
    out[end] = "0";
    findAllSequences(diff - 1, out, start + 1, end - 1);
 
# Driver program
 
# input number
n = 2;
 
# allocate string containing 2*n characters
out=[""]*(2*n);
 
findAllSequences(0, out, 0, 2*n - 1);
 
# This code is contributed by mits

C#

// C# program to print even length binary
// sequences whose sum of first and second
// half bits is same
using System;
 
class GFG {
     
    // Function to print even length binary
    // sequences whose sum of first and
    // second half bits is same
 
    // diff --> difference between sums of
    // first n bits
    // and last n bits
    // out --> output array
    // start --> starting index
    // end --> ending index
    static void findAllSequences(int diff,
            char []outt, int start, int end)
    {
         
        // We can"t cover difference of
        // more than n with 2n bits
        if (Math.Abs(diff) > (end - start
                                   + 1) / 2)
            return;
 
        // if all bits are filled
        if (start > end)
        {
             
            // if sum of first n bits and
            // last n bits are same
            if (diff == 0)
            {
                Console.Write(outt);
                Console.Write(" ");
            }
            return;
        }
 
        // fill first bit as 0 and last bit
        // as 1
        outt[start] = "0";
        outt[end] = "1";
        findAllSequences(diff + 1, outt,
                        start + 1, end - 1);
 
        // fill first and last bits as 1
        outt[start] = outt[end] = "1";
        findAllSequences(diff, outt,
                        start + 1, end - 1);
 
        // fill first and last bits as 0
        outt[start] = outt[end] = "0";
        findAllSequences(diff, outt,
                         start + 1, end - 1);
 
        // fill first bit as 1 and last
        // bit as 0
        outt[start] = "1";
        outt[end] = "0";
        findAllSequences(diff - 1, outt,
                         start + 1, end - 1);
    }
     
    // Driver program
    public static void Main ()
    {
         
        // input number
        int n = 2;
 
        // allocate string containing 2*n
        // characters
        char []outt = new char[2 * n + 1];
 
        // null terminate output array
        outt[2 * n] = "";
 
        findAllSequences(0, outt, 0, 2*n - 1);
    }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// PHP program to print even length binary sequences
// whose sum of first and second half bits is same
 
// Function to print even length binary sequences
// whose sum of first and second half bits is same
 
// diff --> difference between sums of first n bits
// and last n bits
// out --> output array
// start --> starting index
// end --> ending index
function findAllSequences($diff, $out, $start, $end)
{
    // We can"t cover difference of more than n with 2n bits
    if (abs($diff) > (int)(($end - $start + 1) / 2))
        return;
 
    // if all bits are filled
    if ($start > $end)
    {
        // if sum of first n bits and last n bits are same
        if ($diff == 0)
            print(implode("",$out)." ");
        return;
    }
 
    // fill first bit as 0 and last bit as 1
    $out[$start] = "0";
    $out[$end] = "1";
    findAllSequences($diff + 1, $out, $start + 1, $end - 1);
 
    // fill first and last bits as 1
    $out[$start] = $out[$end] = "1";
    findAllSequences($diff, $out, $start + 1, $end - 1);
 
    // fill first and last bits as 0
    $out[$start] = $out[$end] = "0";
    findAllSequences($diff, $out, $start + 1, $end - 1);
 
    // fill first bit as 1 and last bit as 0
    $out[$start] = "1";
    $out[$end] = "0";
    findAllSequences($diff - 1, $out, $start + 1, $end - 1);
}
 
// Driver program
 
    // input number
    $n = 2;
 
    // allocate string containing 2*n characters
    $out=array_fill(0,2*$n,"");
 
    findAllSequences(0, $out, 0, 2*$n - 1);
 
// This code is contributed by chandan_jnu
?>

Выход:

0101 1111 1001 0110 0000 1010

Эта статья предоставлена Адитьей Гоэлем . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью, используя write.geeksforgeeks.org, или отправить свою статью по электронной почте: deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022
Amazon SDE Sheet: вопросы и ответы на собеседовании
12 Декабря, 2022