{"id":2023,"date":"2020-07-01T09:51:13","date_gmt":"2020-07-01T09:51:13","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2023"},"modified":"2022-05-23T11:24:37","modified_gmt":"2022-05-23T11:24:37","slug":"binary-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/binary-list\/","title":{"rendered":"Binary list"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Basic Manipulation<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Easy <\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given a linked list of N<\/code> nodes, each node containing binary bit either 0<\/code> or 1<\/code> as a character. Your task is to arrange nodes in such a way that no two consecutive nodes contain the same bit.<\/p>\n

NOTE<\/em><\/strong> : The list must start from 0<\/code> if there is more than one bit. <\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example:<\/h4>\n
Input : 100101\n\nOutput: 010101\n\nExplaination : As count of 0's and 1's are equal i.e. 3, so they can be arranged accordingly.<\/code><\/pre>\n
Input : 11001\n\nOutput: -1\n\nExplaination : As count of 1's is greater than count of 0's, given string cannot be arranged in the required fashion.<\/code><\/pre>\n
OBSERVATION :<\/h3>\n
\n
We can arrange our string in the required fashion if any of the two conditions are met – <\/p>\n
    \n
  • \n
    count of 0<\/code>‘s is equal to count of 1<\/code>‘s <\/p>\n<\/li>\n
  • \n
    count of 0<\/code>‘s is equal to count of 1<\/code>‘s + 1<\/code><\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
    SOLVING APPROACH:<\/h3>\n
    \n
      \n
    1. Calculate the count of 0<\/code>‘s and 1<\/code>‘s in zeros<\/code> and ones<\/code>.  <\/li>\n
    2. Check if the string is empty or contains only 1<\/code> char, in this case our string is already arranged so return.<\/li>\n
    3. Check if zeros<\/code> = ones<\/code> or zeros<\/code> = ones + 1<\/code>, if true one-by-one keep assigning the values of 0<\/code> and 1<\/code> to the string linearly. Else return.<\/li>\n<\/ol>\n<\/blockquote>\n
      SOLUTIONS:<\/h3>\n
      \t\t\t\t\t\t