{"id":1983,"date":"2020-06-14T15:23:03","date_gmt":"2020-06-14T15:23:03","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1983"},"modified":"2022-05-18T08:43:08","modified_gmt":"2022-05-18T08:43:08","slug":"time-bits","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/time-bits\/","title":{"rendered":"Time Bits"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Back Tracking<\/p>\n<\/blockquote>\n

Difficulty Level<\/h4>\n
\n

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

Problem Statement :<\/h3>\n
\n

Given n<\/code> set bits, we have to determine all the time that can be represented by those number of set bits. Hour (0 to 11) can be represented by 4<\/code> bits and Minutes (0 to 59) can be represented by 6<\/code> bits.<\/p>\n<\/blockquote>\n

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

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

There can be atmost 10<\/code> set bits , 4<\/code> bits for hour and 6<\/code> bits for minutes. Idea is to set (1<\/code>) every bit once and see if the generated value is a valid value for hour (0 to 11) or minute (0 to 59). If it is valid we will consider it else try other combinations which are valid.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Description :<\/h4>\n
\n

We need to explore all the possible combinations for set bits which can be solved with backtracking<\/strong>.
\nBacktracking<\/strong> is the approach to solve the problem by testing all possible combinations. If any subproblem does not fit the given constraint then we discard the complete subproblem, moves a step back then try other remaining possible combinations. Backtracking algorithm is generally exponential in time.
\nThere can be atmost 10<\/code> set bits so we can use an array str[]<\/code> of size 10<\/code>. First 6<\/code> bits in str<\/code> will be reserved for minute<\/strong> and next 4<\/code> bits for hour<\/strong>. We have to try all the combinations for set bits with the given n<\/code> number of bits, so we will set every bit of str<\/code> as 1<\/code> once and calculate hour and minute values, if the values lie in the range 0-11<\/code> & 0-59<\/code> respectively, we will keep this combination of set bit and recur for the next index of str<\/code> to to try other combinations.
\nWe see every index in str<\/code> has two possible cases:<\/p>\n

    \n
  1. Set the bit as 1<\/code><\/li>\n
  2. Set the bit as 0<\/code> (initial state)<\/li>\n<\/ol>\n<\/blockquote>\n

    Algorithm :<\/h3>\n

    backtrack():<\/h4>\n
      \n
    1. calculate hour<\/strong> & minute<\/strong> values, if it is valid proceed, else return.<\/li>\n
    2. if n==0<\/code>, print the time in hours<\/strong> & minutes<\/strong>.<\/li>\n
    3. else, for every k=index<\/code> to 10<\/code> :
      \n
      \n
        \n
      • set str[k]<\/code> as 1<\/code>.<\/li>\n
      • call backtrack(str,index+1,n-1)<\/strong>.<\/li>\n
      • set str[k]<\/code> as 0<\/code>.<\/li>\n<\/ul>\n<\/blockquote>\n<\/li>\n<\/ol>\n

        Complexity Analysis :<\/h3>\n
        \n

        For every index i<\/code> we are first setting the ith<\/code> bit high , then setting it low to look for different bit combinations.<\/p>\n<\/blockquote>\n

        Solutions:<\/h3>\n\t\t\t\t\t\t