Find all even length binary sequences with same sum of first and second half bits - GeeksforGeeks



Find all even length binary sequences with same sum of first and second half bits - GeeksforGeeks

Given a number n, find all binary sequences of length 2n such that sum of first n bits is same as sum of last n bits.

Examples:

Input:  N = 2  Output:   0101 1111 1001 0110 0000 1010     Input:  N = 3  Output:    011011 001001 011101 010001 101011 111111  110011 101101 100001 110101 001010 011110   010010 001100 000000 010100 101110 100010   110110 100100   

We strongly recommend you to minimize your browser and try this yourself first.

The idea is to fix first and last bits and then recur for remaining 2*(n-1) bits. There are four possibilities when we fix first and last bits –

  1. First and last bits are 1, remaining n – 1 bits on both sides should also have the same sum.
  2. First and last bits are 0, remaining n – 1 bits on both sides should also have the same sum.
  3. First bit is 1 and last bit is 0, sum of remaining n – 1 bits on left side should be 1 less than the sum n-1 bits on right side.
  4. First bit is 0 and last bit is 1, sum of remaining n – 1 bits on left side should be 1 more than the sum n-1 bits on right side.


Read full article from Find all even length binary sequences with same sum of first and second half bits - GeeksforGeeks


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts