Minimum length String with Sum of the alphabetical values of the characters equal to N
Given an integer N, the task is to find the minimum length string whose sum of each character (As a = 1, b = 2, … z = 26) equals to N.
Examples:
Input: N = 5 Output: e 5 can be represented as "aac" or "ad" or "e" etc But we will take e as it is the minimum length Input: N = 34 Output: zj
Approach:
- To minimise the length of the String, Greedy Approach will be used.
- By Greedy Approach, the solution will be very simple.
- The minimum length of the String will be
N/26 + 1 => if N % 26 != 0 N/26 => if N % 26 == 0
- And the minimum string can be found as
(N/26 times z) + (N%26) => if N % 26 != 0 (N/26 times z) => if N % 26 == 0
Below is the implementation of the above approach:
C++
// C++ program to find the Minimum length String // with Sum of the alphabetical values // of the characters equal to N #include <bits/stdc++.h> using namespace std; // Function to find the minimum length int minLength( int n) { int ans = n / 26; if (n % 26 != 0) ans++; return ans; } // Function to find the minimum length String string minString( int n) { int ans = n / 26; string res = "" ; while (ans--) { res = res + "z" ; } if (n % 26 != 0) { res = res + ( char )((n % 26) + 96); } return res; } // Driver code int main() { int n = 50; cout << minLength(n) << endl << minString(n); return 0; } |
Java
// Java program to find the Minimum length String // with Sum of the alphabetical values // of the characters equal to N class GFG { // Function to find the minimum length static int minLength( int n) { int ans = n / 26 ; if (n % 26 != 0 ) ans++; return ans; } // Function to find the minimum length String static String minString( int n) { int ans = n / 26 ; String res = "" ; while (ans-- != 0 ) { res = res + "z" ; } if (n % 26 != 0 ) { res = res + ( char )((n % 26 ) + 96 ); } return res; } // Driver code public static void main (String[] args) { int n = 50 ; System.out.println(minLength(n)); System.out.println(minString(n)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 program to find the Minimum length String # with Sum of the alphabetical values # of the characters equal to N # Function to find the minimum length def minLength(n): ans = n / / 26 if (n % 26 ! = 0 ): ans + = 1 return ans # Function to find the minimum length String def minString(n): ans = n / / 26 res = "" while (ans): res = res + "z" ans - = 1 if (n % 26 ! = 0 ): res = res + chr ((n % 26 ) + 96 ) return res # Driver code n = 50 ; print (minLength(n)) print (minString(n)) # This code is contributed by Mohit Kumar |
C#
// C# iprogram to find the Minimum length String // with Sum of the alphabetical values // of the characters equal to N using System; class GFG { // Function to find the minimum length static int minLength( int n) { int ans = n / 26; if (n % 26 != 0) ans++; return ans; } // Function to find the minimum length String static String minString( int n) { int ans = n / 26; String res = "" ; while (ans-- != 0) { res = res + "z" ; } if (n % 26 != 0) { res = res + ( char )((n % 26) + 96); } return res; } // Driver code public static void Main (String[] args) { int n = 50; Console.WriteLine(minLength(n)); Console.WriteLine(minString(n)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program to find the Minimum length String // with Sum of the alphabetical values // of the characters equal to N // Function to find the minimum length function minLength(n) { var ans = parseInt(n / 26); if (n % 26 != 0) ans++; return ans; } // Function to find the minimum length String function minString(n) { var ans = parseInt(n / 26); var res = "" ; while (ans--) { res = res + "z" ; } if (n % 26 != 0) { res = res + String.fromCharCode((n % 26) + 96); } return res; } // Driver code var n = 50; document.write(minLength(n)+ "<br>" + minString(n)); </script> |
Output:
2 zx
Time Complexity: O(x) where x = n/26
Auxiliary Space: O(x+1) where x = n/26