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!

# Time Bits

Last Updated on May 18, 2022 by Ria Pathak

Back Tracking

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.

See original problem statement here

### 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{

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();