View Dialogue

Enhance Article

Save Article

Like Article

Given two integers M and N the duty is to assemble a binary palindromic string consisting of M occurrences of 0s and N occurrences of 1s.

Examples:

Enter: M = 4, N = 3
Output: 0011100
Clarification: The string 0011100 is palindrome containing 
4 occurrences of ‘0’ and three occurrences of ‘1’.

Enter: M = 3, N = 3
Output: -1 

 

Strategy: 

For the string to be a palindrome, atleast one amongst M and N needs to be even, in any other case if each M and N are odd then string cannot be a palindrome.

Observe the under steps to unravel the issue:

  • If each M and N are odd then print -1.
  • If N is Even, print ‘1’ N/2 occasions, then print ‘0’ M occasions, then once more print ‘1’ N/2 occasions.
  • If M is Even, print ‘0’ M/2 occasions, then print ‘1’ N occasions, then once more print ‘0’ M/2 occasions.

Under is the implementation of the above strategy: 

C++

#embrace <iostream>

utilizing namespace std;

  

string buildString(int M, int N, char P, char Q)

{

    string res = "";

    for (int i = 0; i < M / 2; i++)

        res += P;

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

        res += Q;

    for (int i = 0; i < M / 2; i++)

        res += P;

    return res;

}

  

string makePalin(int M, int N)

{

    

    

    

    if ((M & 1) && (N & 1)) {

        return "-1";

    }

    else {

        string ans = "";

        if (N & 1) {

            ans = buildString(M, N, '0', '1');

        }

        else {

            ans = buildString(N, M, '1', '0');

        }

        return ans;

    }

}

  

int important()

{

    int M = 4;

    int N = 3;

  

    

    cout << makePalin(M, N);

    return 0;

}

Time Complexity: O(M+N)
Auxiliary Area: O(1)

    By admin

    Leave a Reply

    Your email address will not be published.