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