Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Backtracking Interview Questions

Time Bits

Prepbytes

Concepts Used

Back Tracking

Difficulty Level

Easy

Problem Statement :

Given n 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 bits and Minutes (0 to 59) can be represented by 6 bits.

Solution Approach :

Introduction :

There can be atmost 10 set bits , 4 bits for hour and 6 bits for minutes. Idea is to set (1) 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.

Description :

We need to explore all the possible combinations for set bits which can be solved with backtracking.
Backtracking 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.
There can be atmost 10 set bits so we can use an array str[] of size 10. First 6 bits in str will be reserved for minute and next 4 bits for hour. We have to try all the combinations for set bits with the given n number of bits, so we will set every bit of str as 1 once and calculate hour and minute values, if the values lie in the range 0-11 & 0-59 respectively, we will keep this combination of set bit and recur for the next index of str to to try other combinations.
We see every index in str has two possible cases:

  1. Set the bit as 1
  2. Set the bit as 0 (initial state)

Algorithm :

backtrack():

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

Complexity Analysis :

For every index i we are first setting the ith bit high , then setting it low to look for different bit combinations.

Solutions:

#include <stdio.h>
    #include<stdlib.h>


      char hour[10];
      char minute[10];

    int b(char bitString[], int n){
         int ret = 0;
         for(int i = 0; i < n; i++)
              if(bitString[i] == '1')
                ret |= 1 << ((n-1)-i);

         return ret;
    }
    void backtrack(char s[], const int start,const int num)
    {

            for(int i=6;i<10;i++)
             hour[i] = s[i];
            int hours = b(hour,10);
            if(hours > 11){
                return;
            }

            for(int j=0;j<6;j++)
                minute[j] = s[j];
            int minutes = b(minute,6);
            if(minutes > 59){
                return;
            }
            if(num==0){
                printf(" %d:%s%d",hours,(minutes < 10 ? "0" : ""),(minutes) );
                return;
            }

            if(start == 10){
                return;
            }

            for(int i=start; i<10; ++i){
                s[i] = '1';
                backtrack(s, i+1, num-1);
                s[i] = '0';
            }
        }


    int main()
    {
      int n;
      scanf("%d",&n);
      char s[]={'0','0','0','0','0','0','0','0','0','0'};
      backtrack(s,0,n);

      return 0;
    }

#include <bits/stdc++.h>
    using namespace std;
    void backtrack(string& s, int start, int num)
    {

            int hours = std::bitset<4>(s.substr(6, 4)).to_ulong();
            if(hours > 11){
                return;
            }
            int minutes = std::bitset<6>(s.substr(0, 6)).to_ulong();
            if(minutes > 59){
                return;
            }
            if(num==0){
                cout<<(to_string(hours) + ":" + (minutes < 10 ? "0" : "") + to_string(minutes))<<" ";
                return;
            }

            if(start == s.length()){
                return;
            }

            for(int i=start; i<10; ++i){
                s[i] = '1';
                backtrack(s, i+1, num-1);
                s[i] = '0';
            }
        }

    int main()
    {    
        int n,m;
        cin>>n;
        string s = "0000000000";
        backtrack(s, 0, n); 
    return 0;
    }

import java.util.*;
import java.io.*;

public class Main{

    public void readBinaryWatch(int num) {
        List<String> result = new ArrayList<>();

        //range 0-3 are hours and range 4-9 are minutes
        int[] arr = {1, 2, 4, 8, 1, 2, 4, 8, 16, 32};
        backtrack(arr, 0, 0, 0, num, result);
    }

    public void backtrack(int[] arr, int position, int hours, int minutes, int limit, List<String> result) {
        if (limit == 0) {

            if(hours <= 11 && minutes <= 59) {
                StringBuilder builder = new StringBuilder();
                builder.append(hours).append(":").append(minutes <= 9 ? "0" + minutes : minutes);
                System.out.print(" "+builder.toString());
            }
            return;
        }

        for (int i = arr.length-1; i >= position; i--) {
            if (isHour(i)) hours += arr[i];
            else minutes += arr[i];

            backtrack(arr, i + 1, hours, minutes, limit - 1, result);

            if (isHour(i)) hours -= arr[i];
            else minutes -= arr[i];
        }
    }

    public boolean isHour(int position) {
        return position >= 0 && position <= 3;
    }
    public static void main(String[] args)
    {
      Scanner sc = new Scanner(System.in);
      List<String> res = new ArrayList<>();
      int n = sc.nextInt();
      Main m = new Main();
      m.readBinaryWatch(n);
      //System.out.print("\n");

    }
}

[forminator_quiz id="1995"]

This article tried to discuss Backtracking. Hope this blog helps you understand and solve the problem. To practice more problems on backtracking you can check out .

Leave a Reply

Close

Related Post