La string numérica lexicográficamente más pequeña que tiene recuentos de dígitos impares

Dado un entero positivo N , la tarea es generar una string numérica lexicográficamente más pequeña de tamaño N que tenga un recuento impar de cada dígito.

Ejemplos:

Entrada: N = 4
Salida: 1112
Explicación:
Los dígitos 1 y 2 tienen un conteo par y es la string lexicográficamente más pequeña posible.

Entrada: N = 5
Salida: 11111
Explicación:
El dígito 1 tiene un conteo impar y es la string lexicográficamente más pequeña posible.

Enfoque: El problema dado se puede resolver basándose en la observación de que si el valor de N es par , entonces la string resultante contiene 1s , (N – 1) número de veces seguido de un solo 2 es la string lexicográfica más pequeña posible. De lo contrario, la string resultante contiene 1s , N número de veces es la string lexicográfica más pequeña posible.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to construct lexicographically
// smallest numeric string having an odd
// count of each characters
string genString(int N)
{
    // Stores the resultant string
    string ans = "";
 
    // If N is even
    if (N % 2 == 0) {
        ans = string(N - 1, '1') + '2';
    }
 
    // Otherwise
    else {
        ans = string(N, '1');
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int N = 5;
    cout << genString(N);
 
    return 0;
}

# python program for the above approach
# Function to construct lexicographically
# smallest numeric string having an odd
# count of each characters
def genString(N):
   
    # Stores the resultant string
    ans = ""
 
    # If N is even
    if (N % 2 == 0) :
        ans = "".join("1" for i in range(N-1))
        ans = ans + "2"
     
    # Otherwise
    else :
        ans = "".join("1" for i in range(N))
     
    return ans
   
# Driver code
if __name__ == "__main__":
    N = 5
    print(genString(N))
 
 
# This code is contributed by anudeep23042002

// C# program for the above approach
using System;
class GFG {
 
    // Function to construct lexicographically
    // smallest numeric string having an odd
    // count of each characters
    static string genString(int N)
    {
       
        // Stores the resultant string
        string ans = "";
 
        // If N is even
        if (N % 2 == 0) {
            for (int i = 0; i < N - 1; i++)
                ans += '1';
            ans += '2';
        }
 
        // Otherwise
        else {
            for (int i = 0; i < N; i++)
                ans += '1';
        }
 
        return ans;
    }
 
    // Driver code
    public static void Main()
    {
        int N = 5;
        Console.WriteLine(genString(N));
    }
}
 
// This code is contributed by ukasp.

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to construct lexicographically
        // smallest numeric string having an odd
        // count of each characters
        function genString(N)
        {
         
            // Stores the resultant string
            let ans = "";
 
            // If N is even
            if (N % 2 == 0) {
                ans = '1'.repeat(N - 1) + '2';
            }
 
            // Otherwise
            else {
                ans = '1'.repeat(N);
            }
 
            return ans;
        }
 
        // Driver code
        let N = 5;
        document.write(genString(N));
 
     // This code is contributed by Potta Lokesh
    </script>

11111

Complejidad temporal: O(N)
Espacio auxiliar: O(N)