Horje
Lexicographically smallest numeric string having odd digit counts

Given a positive integer N, the task is to generate a lexicographically smallest numeric string of size N having an odd count of each digit.

Examples:

Input: N = 4
Output: 1112
Explanation:
Digit 1 and 2 both have an even count and is the lexicographically smallest string possible.

Input: N = 5
Output: 11111
Explanation:
Digit 1 has an odd count and is the lexicographically smallest string possible.

Approach: The given problem can be solved based on the observation that if the value of N is even, then the resulting string contains 1s, (N – 1) number of times followed by a single 2 is the smallest lexicographic string possible. Otherwise, the resulting string contains 1s, N number of times is the smallest lexicographic string possible.

Below is the implementation of the above approach:

C++14

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

Python3

# 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#

// 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.

Javascript

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

Java

import java.io.*;
import java.util.*;
class GFG {
    // Function to construct lexicographically
    // smallest numeric string having an odd
    // count of each characters
    public static String genString(int N) {
        // Stores the resultant string
        String ans = "";
 
        // If N is even
        if (N % 2 == 0) {
            // Construct a string of N-1 1's and add a 2 at the end
            ans = new String(new char[N - 1]).replace("\0", "1") + "2";
        }
 
        // Otherwise
        else {
            // Construct a string of N 1's
            ans = new String(new char[N]).replace("\0", "1");
        }
 
        return ans;
    }
 
    public static void main(String[] args) {
 
        int N = 5;
        System.out.println(genString(N));
        
    }
}
// This code is contributed by Shivam Tiwari

Output: 

11111

 

Time Complexity: O(N)
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

Strings

Related
Sum of the shortest distance between all 0s to 1 in given binary string Sum of the shortest distance between all 0s to 1 in given binary string
Average value of set bit count in given Binary string after performing all possible choices of K operations Average value of set bit count in given Binary string after performing all possible choices of K operations
K-th Lexicographically smallest binary string with A 0s and B 1s K-th Lexicographically smallest binary string with A 0s and B 1s
Check if a Regular Bracket Sequence can be formed with concatenation of given strings Check if a Regular Bracket Sequence can be formed with concatenation of given strings
Find any permutation of Binary String of given size not present in Array Find any permutation of Binary String of given size not present in Array

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje