1. ## Random Password Generator

Arnab has an online account which requires him to change
his password every month. He wants to create a program to
help him generate the password.
He comes up with an algorithm to generate all combinations
of strings of a fixed length using only the starting letter and
ending letter of his name (A & B). To randomize the password selection, he then sorts the list in
lexicographical (ascending) order and chooses a string at a random position.
Help Arnab implement this algorithm.
For example:
Consider the length of password to be 3 for which Arnab generates all the combinations of strings. He
sorts them in ascending order and then picks a password at 2nd position.
The sorted possible strings of length 3 with characters A and B are as follows:
AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB
The string at index 2 is AAB

Input

The first line contains the length N of the password.
The second line contains the index M of the string to be picked from the sorted list of strings (consider the
first item as index 1).

Output

Print the chosen password.

Constraints

0 < N < 10
0 < M < 2^N

Sample Input #1

3
2

Sample Output #1

AAB

Sample Input #2

4
7

Sample Output #2

ABBA

This is my solution but I'm not sure if this is the simplest way to achieve the end solution. Is there a better way to do this?

Code:
#include <iostream>

using namespace std;

int main()
{
int N , M , Total_Possibilities = 1 , temp;

string result;

cin >> N >> M;

temp = N;

while ( temp-- > 0 )
{
Total_Possibilities*=2;
}

for ( temp = 0 ; temp < N ; temp++ )
{
Total_Possibilities/=2;

if ( M <= Total_Possibilities )
result += "A";

else
{
M -= Total_Possibilities;
result += "B";
}
}

cout << endl << result;

return 0;
}
My first attempt was to use an string array of size 2^N which contains the possibilities in the proper lexicographical series and then displaying the string at the Mth position. But, as advised by @Salem in my Last Man Standing Thread to not just hop into the question for the sake of doing it but instead looking for patterns and clues behind simpler solutions, I wrote down the possibilities and figured out my current solution. This is the best I could achieve but I still have a feeling that the solution may actually be simpler. So if anyone can state it out, I might give it another try. Thanks

2. The answer is just the binary representation of M - 1 given in N bits, where 0 is represented by A and 1 by B.
Code:
#include <iostream>

int main() {
int n, m;
std::cin >> n >> m;
--m;
for (int x = 1 << n; x; x /= 2) {
if (m / x) {
std::cout << 'B';
m -= x;
}
else
std::cout << 'A';
}
std::cout << '\n';
}

3. The constraints seem wrong because they exclude the last index. Using the given example, it's not possible to pick "BBB" because that's at index 8 (M = 8), but M must be less than 8. The constraints should be:

0 < N < 10
0 < M <= 2^N

(This doesn't affect your solution, though.)

4. I haven't learnt how to do use binary representations and neither do I know what (1 << n) means but I'm definitely gonna look it up now.

Also, even though I didn't understand the working, I copied the code and compiled it with the latest version GNU GCC and the code seems to be working fine except that when I do something like

INPUT: 4 16 (or any other number <=16)

OUTPUT: ABBBB (or the correct representation of the number <=16) except that the extra "A" is displayed in the front of every correct answer.

Thanks for your solution, it gave me a new way to approach this sort of stuff

5. Edit: I read a lot more about it in the past hour and all I can say is it's a shame we are not taught basic things like this in school. I've been learning C++ for over a year and I had no clue about this. I modified the code slightly and now it works perfectly without the extra "A". Thanks a lot!

Popular pages Recent additions