Last Updated on May 18, 2022 by Ria Pathak
Concepts Used
Back Tracking
Difficulty Level
Easy
Problem Statement :
Given
nset 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 by4bits and Minutes (0 to 59) can be represented by6bits.
See original problem statement here
Solution Approach :
Introduction :
There can be atmost
10set bits ,4bits for hour and6bits 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 atmost10set bits so we can use an arraystr[]of size10. First6bits instrwill be reserved for minute and next4bits for hour. We have to try all the combinations for set bits with the givennnumber of bits, so we will set every bit ofstras1once and calculate hour and minute values, if the values lie in the range0-11&0-59respectively, we will keep this combination of set bit and recur for the next index ofstrto to try other combinations.
We see every index instrhas two possible cases:
- Set the bit as
1- Set the bit as
0(initial state)
Algorithm :
backtrack():
- calculate hour & minute values, if it is valid proceed, else return.
- if
n==0, print the time in hours & minutes. - else, for every
k=indexto10:
- set
str[k]as1. - call backtrack(str,index+1,n-1).
- set
str[k]as0.
- set
Complexity Analysis :
For every index
iwe are first setting theithbit 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 MYCODE | Competitive Programming.