The lexicographically largest string whose sum of characters equals N

Problem Statement

We are given a positive integer num. We need to find a string consisting of lowercase letters such that the sum of all characters in the string is equal to num, and the string is the largest in lexicographic order. Here, ‘a’ = 1, ‘b’ = 2, ‘c’ = 3, ‘d’ = 4, …., ‘z’ = 26.

We need to use the "z" character at the beginning of the string to create the largest dictionary string. Finally, we need to use the last character based on the num % 26 value.

Example

enter

num = 30

Output

‘zd’

The Chinese translation of

Explanation

is:

Explanation

'zd' is the largest lexicographic string with a character sum of 30 (z = 26 d = 4).

enter

3

Output

‘c’

The Chinese translation of

Explanation

is:

Explanation

‘c’ represents 3 itself.

enter

130

Output

‘zzzzz’

The Chinese translation of

Explanation

is:

Explanation

The sum of the values ​​of each character 'zzzzz' is 130.

method 1

This method will use a while loop to create a result string. We will iterate until a number has a value greater than or equal to 26, on each iteration we will add 'z' to the string and subtract 26 from the number. Finally, we will add a character to the string based on the remainder.

algorithm

• Step 1 - Execute the findString() function by passing a numeric value as parameter.

• Step 2 - Initialize the result variable of type string with an empty string to store the result string.

• Step 3 - Use a while loop to iterate until the value of 'num' is greater than or equal to 26.

• Step 4 - In the while loop, add the character 'z' to the resulting string.

• Step 5 - Subtract 26 from the value of a number.

• Step 6 - When the while loop iteration is completed, check whether the value of num is greater than 0. If so, append the last character to the string based on the value of the 'num' variable.

• Step 7 - Return the result string.

The Chinese translation of

Example

is:

Example

#include <bits/stdc++.h>
using namespace std;

// function to find the resultant string
string findString(int num) {
   // variable to store the resultant string
   string result = "";
   // using a while loop to find the resultant string
   while (num >= 26) {
      // append z to the resultant string
      result += 'z';
      // Decrease the number by 26
      num -= 26;
   }
   // Convert the remaining number to char and append to the resultant string
   if(num != 0) {
      result += char(num + 'a' - 1);
   }
   return result;
}

int main() {
   int num = 96;
   cout << "The resultant string is " << findString(num);
   return 0;
}

Output

The resultant string is zzzr

• Time complexity - O(num), because the while loop runs num/26 times, which is equal to O(num).

• Space complexity - O(num), because a string can contain up to (num/26 1) characters.

Method 2

In this method, we will create a string of length N using the String() constructor. We will use modulo and division operators to get the total number of z's in the string.

algorithm

• Step 1 - Define the "totalZ" variable and initialize it with num/26.

• Step 2 - Define the 'rem' variable and initialize it with 'num%26'.

• Step 3 - Use it to create a string() constructor by passing 'totalZ' as the first argument and 'z' as the second argument to A string of totalZ' 'z' characters. At the same time, append it to the 'result' string.

• Step 4 - If the value of 'rem' is not equal to 0, append the last character to the string based on the value of the 'rem' variable.

• Step 5 - Return the 'result' string.

The Chinese translation of

Example

is:

Example

#include <bits/stdc++.h>
using namespace std;
// function to find the resultant string
string findString(int num) {
   // variable to store the resultant string
   string result = "";
   // variable to store the number of z's
   int totalZ = num / 26;
   // variable to store the remainder
   int rem = num % 26;
   // Using the string constructor to create a string with total number of totalZ 'z'.
   result += string(totalZ, 'z');
   // If the remainder is non-zero, then add the corresponding character
   if(rem != 0) {
      result += char(rem + 'a' - 1);
   }
   return result;
}
int main(){
   int num = 52;
   cout << "The resultant string is " << findString(num);
   return 0;
}

Output

The resultant string is zz

• Time complexity - O(num) As a string constructor, create a string containing totalz characters.

• Space complexity - O(num)

in conclusion

We learned two ways to convert numbers to strings. We have used while loop in the first method and string() constructor in the second method. However, both methods have the same space and time complexity, but the second method is more readable.

The above is the detailed content of The lexicographically largest string whose sum of characters equals N. For more information, please follow other related articles on the PHP Chinese website!