UAV 729 The Hamming Distance Backtracking Problem

This problem simply states that we have to print all permutation of binary number of length N with M number of 1’s. Let us see the below example test case.

Sample Input
1
4 2
Sample Output
0011
0101
0110
1001
1010
1100

Sample Input

4 2

Sample Output

0011

0101

0110

1001

1010

1100

Test case explanation
N is 4 ( it means 4 length of binary number)
M is 2 ( it means number of 1’s in binary number)
Observation:
Look at the first output ( 0011) , the last two digit of first output is 1 1. The next output is the all combinations of first output.

How to solve:
(1) take a string of length N , filled with 0.
(2) Append 1 1 to the end of the string.
(3) Print all combinations of string ( achieved at step 2).

Problem link:
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=670

Solution:

#include<algorithm>
#include<cstdio>
#include<iostream>
 
using namespace std;
 
int T=0, N=0, M=0;
string s;
 
int main() {
    
    // read number of test case 
    cin>>T;
    for(int test=0; test < T; test++) 
    {
        // read length of binary number(N) and number of(M) 1's
        cin>>N>>M;
        
        // make first string 
        s = "";
        for(int i = 0; i < N; i++) {
            if(i < N - M)
                s += '0';
            else
                s += '1';
        }
        // permutation of string s
        do
        {
          cout << s << endl;
        } while(next_permutation(s.begin(), s.end()));
 
    }
 return 0;
}

#include<algorithm>

#include<cstdio>

#include<iostream>

using namespace std;

int T=0, N=0, M=0;

string s;

int main() {

// read number of test case

cin>>T;

for(int test=0; test < T; test++)

{

// read length of binary number(N) and number of(M) 1's

cin>>N>>M;

// make first string

s = "";

for(int i = 0; i < N; i++) {

if(i < N - M)

s += '0';

else

s += '1';

}

// permutation of string s

{

cout << s << endl;

} while(next_permutation(s.begin(), s.end()));

}

return 0;

}

UAV 729 The Hamming Distance Backtracking Problem

WE RECOMMEND RELATED POST

No Comments Yet

Leave a Reply Cancel reply