Найдите все двоичные последовательности четной длины с одинаковой суммой первой и второй половины битов
Учитывая число 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
Идея состоит в том, чтобы исправить первый и последний бит, а затем повторить оставшиеся 2 * (n-1) бит. Когда мы исправляем первый и последний бит, есть четыре возможности:
- Первый и последний биты равны 1, оставшиеся n - 1 бит с обеих сторон также должны иметь одинаковую сумму.
- Первый и последний биты равны 0, оставшиеся n - 1 бит с обеих сторон также должны иметь одинаковую сумму.
- Первый бит равен 1, а последний бит равен 0, сумма оставшихся n - 1 бит на левой стороне должна быть на 1 меньше суммы n-1 бит на правой стороне.
- Первый бит равен 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.