String Pair

Moderate
0/80
profile
Contributed by
20 upvotes

Problem statement

One person hands over the list of digits to Mr. String, But Mr. String understands only strings. Within strings also he understands only vowels. Mr. String needs your help to find the total number of pairs that add up to a certain digit 'D’. The rules to calculate digit ‘D’ is as follows:

Take all digits and convert them into their textual representation. Next, sum up the number of vowels i.e. {a, e, i, o, u} from all textual representations. This sum is the digit ‘D’. Now, once digit ‘D’ is known find out all unordered pairs of numbers in input whose sum is equal to ‘D’.

For Example: 
If N=5 and array elements are [1, 2, 3, 4, 5]. 
1 -> one -> o, e 
2 -> two -> o 
3 -> three -> e, e 
4 -> four -> o, u 
5 -> five – > i, e 
Thus, count of vowels in textual representation of numbers in input = {2 + 1 + 2 + 2 + 2} = 9. Number 9 is the digit ‘D’ referred to in the section above. Now from given list of number {1,2,3,4,5} -> find all pairs that sum up to 9. Upon processing this we know that only a single unordered pair {4, 5} sum up to 9. Hence the answer is 1.
However, output specification requires you to print the textual representation of number 1 which is “one”. Hence the output is “one”.
Note: 
Pairs {4, 5} or {5, 4} both sum up to 9. But since we are asking to count only unordered pairs, the number of unordered pairs in this combination is only one.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer, 'T’, denoting the number of test cases.

The first line of each test case will contain a single integer ‘N’’, denoting the size of the array.

The second line of each test case contains ‘N’ space-separated integers denoting elements of the array.
Output Format : 
Lower case representation of the textual representation of the number of pairs in input that sum up to digit ‘D’.
Note: 
If the count exceeds 100 print “greater 100”.

Print a separate line for each test case.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 1000
1 <= nums[i] <= 100

Time limit: 1 sec
Sample Input 1 :
2
5
1 2 3 4 5
3
7 4 2
Sample output 1 :
one
zero
Explanation For Sample Output 1:
For the first test case,
N=5 and array elements are [1, 2, 3, 4, 5]. 
1 -> one -> o, e 
2 -> two -> o 
3 -> three -> e, e 
4 -> four -> o, u 
5 -> five – > i, e 
Thus, count of vowels in textual representation of numbers in input = {2 + 1 + 2 + 2 + 2} = 9. Number 9 is the digit D referred to in the section above. Now from given list of number {1,2,3,4,5} -> find all pairs that sum up to 9. Upon processing this we know that only a single unordered pair {4, 5} sum up to 9. Hence the answer is 1.
However, output specification requires you to print the textual representation of number 1 which is “one”. Hence the output is “one”. 

For the second test case,
N=3 and array elements are [7, 4, 2]. 
7 -> seven -> e, e 
4 -> four -> o, u 
2 -> two -> o 
Thus, count of vowels in textual representation of numbers in input = {2 + 2 + 1} = 5. Number 5 is the digit ‘D’ referred to in the section above. Since no pairs add up to 5, the answer is 0. The textual representation of 0 is “zero”. Hence the output is “zero”.
Sample Input 2 :
2
3 
12 3 2
2 
3 1
Sample output 2 :
one
one
Hint

Convert every digit from 1 to 100 into its textual representation.

Approaches (2)
Brute Force

The basic idea of this approach is to convert every digit from 1 to 100 into its textual representation, then for every digit in the given array check how many vowels are there in its textual representation, sum all of those numbers let it be “sum” then the problem is how many unordered pairs are there in the given array whose sum is equal to “sum” which we can solve by considering every possible pair i,j such that i<j.

 

Here is the algorithm:

  • is_vowel function:
    • If c is ‘a’ or ‘e’ or ‘i’ or ‘u’
      • Return 1.
    • Return 0.
  • given function:
    • Make a vector of string “textualRepresentation”, in which textualRepresentaion[i] represents the textual representation of the non-negative integer ‘i’.
    • Declare a variable “sum” and initialize it with 0.
    • Iterate over the given array (say iterator ‘i’)
      • text=textualRepresentation[num[i]].
      • Iterate over the “text” string (say iterator ‘i’)
        • If text[i] is vowel
          • sum+=1.
    • Declare a variable “count_pairs” and initialize it with 0.
    • Iterate over the given array (say iterator ‘i’)
      • Iterate over the given array from ‘i’+1 to n-1 (say iterator ‘j’)
        • If num[i]+num[j] is equal to sum
          • count_pairs+=1.
    • If count_pairs is less than or equal to 100
      • return textualRepresentation[count_pairs].
    • Else
      • return "greater 100".
Time Complexity

O( N ^ 2 ), where ‘N’ is the size of the array.
 

For finding the sum of vowels it will take O(N * length_of_textual_representation) where the length of textual representation is a constant. For finding the number of pairs that sum up to “sum” it will take O(N ^ 2) time. So time complexity will be O( N^2 ).

Space Complexity

O(1).

 

As we are using a constant space to store 100 textual representations.

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