String Sum

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
3 upvotes
Asked in company
Facebook

Problem statement

Dhoni is the security administrator of the company you are working and you are junior to him. Dhoni’s job is to come up with new and innovative encryption algorithms to encrypt the data while sending it to the receiver.

He came up with a new encryption algorithm as follows: Let’s suppose there is a string ‘STR’ of length ‘N’ which consists of lowercase English letters and numbers from ‘0’ to ‘9’.

The above algorithm will first find the total of all the digits occurring in the string ‘STR’ and remove them from the string, then will sort the whole string in alphabetical order and push all digits sum at the end of the above-generated string. In case there is no digit present in the given string, we don't add anything at the end.

He is analyzing how effective this algorithm will be so he asked you to automate this process so that he gets the results quicker.

So can you help hip to automate this process?.

NOTE: The sum of numbers occurring in the string may have more than one digit.

EXAMPLE : 
Input: ‘N’ = 7, ‘STR’ = ac2bew3

Output: abcew5
In this case, the digit occurring in the ‘STR’ is ‘2’ and ‘3’. Their sum is ‘5’. And when we sort the letters in alphabetical order we get “abcew”. Hence the concatenation of both is “abcew5”.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', the number of test cases.

Each test case consists of two lines.

The first line of input contains one integer, ‘N’ the length of the string ‘STR’.

Followed by a line containing the string ‘STR’ of length ‘N’.
Output format : 
For each test case, print the final string obtained after performing the mentioned steps.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5
‘STR’ consists of lowercase letters or digits.
It is guaranteed that sum of ‘N’ over all test cases is <= 10^5
Time Limit: 1 sec
Sample Input 1 :
2
4
x3a8
5
36zab
Sample Output 1 :
ax11
abz9
Explanation Of Sample Input 1 :
For the first test case, the digits in the given string are ‘3’ and ‘8’. Their sum is ‘11’. And when we sort the letters in alphabetical order we get “ax”. Hence the concatenation of both is “ax11”.

Hence, the output will be: ax11

For the second test case, the digits in the given string are ‘3’ and ‘6’. Their sum is ‘9’. And when we sort the letters in alphabetical order we get “abz”. Hence the concatenation of both is “abz9”.

Hence, the output will be: abz9
Sample Input 2 :
2
5
78345
5
zycba
Sample Output 2 :
27
abcyz
Hint

Can we divide the problem into two parts?.

Approaches (2)
Sorting approach

The idea for this approach is to divide the whole process into two parts. The first part will involve doing the sum of all the digits present in the string ‘STR’. The second part will involve the ordering of letters in alphabetical order. And then we concatenate the results of both parts and get the final result.

 

To solve the first part we will iterate on the given string and whenever we find a digit we add it to a variable sum. And then we create a string of that number.
 

For the second part, we will first, create a new string that will only contain all the letters in the given string ‘STR’. Then we will sort the letters in alphabetical order.
 

We can sort the letters in alphabetical order using any O(N*log(N)) algorithm for better time complexity.
 

Then we merge the results of both parts and return them.
 

Algorithm:
 

// The function will return true if the given character is a number.

Int isDigit(X)

  • If X lies in the range ‘0’ to ‘9’.
    • Return the value of ‘X’ in the decimal system.
  • Return ‘-1’.

 

// The function will return the final string after performing given operations.

String stringSum(N, STR)

  • Initialize a variable named ‘SUM’ with the value of ‘0’.
  • Initialize a variable names ‘digitFound’ with the value of ‘FALSE’.
  • Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
    • Initialize a variable named ‘DIGIT’ with the value of ‘isDigit(STR[i])’.
    • If ‘DIGIT != -1’
      • Add ‘DIGIT’ to ‘SUM’.
      • Assign ‘digitFound’ the value of ‘TRUE’.
  • Initialize a string with the name ‘charStr’.
  • Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
    • Initialize a variable named ‘DIGIT’ with the value of ‘isDigit(STR[i])’.
    • If ‘DIGIT == -1’
      • Add ‘STR[i]’ to ‘charStr’.
  • Sort the ‘charStr’ string in alphabetical order.
  • If ‘digitFound == TRUE’
    • Add the string formed by converting ‘SUM’ into the string format to the ‘charStr’ string.
  • Return ‘charStr’.
Time Complexity

O(N*(log(N))), Where ‘N’ is the input integer.

As we are sorting the string formed by the letters given in the string ‘STR’ in alphabetical order using an O(N*(log(N))) algorithm, the time complexity will be O(N*(log(N)))

Space Complexity

O(N), Where ‘N’ is the input integer.

 

As we are using the extra space to create the new string formed by the letters ‘charStr’ and sum separately and then combining them which in the worst case can have a length of ‘N’, the space complexity will be O(N).

Code Solution
(100% EXP penalty)
String Sum
Full screen
Console