Thread: 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

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';
}