String Pairs | TCS Codevita 2020
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 which add up to a certain digit D.
The rules to calculate digit D are 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 representation. This sum is digit D.
- Now, once digit D is known find out all unordered pairs of numbers in input whose sum is equal to D.
Problem Statement: Given an array arr[] consisting of N ( 1 ? N ? 100 ) integers, the task is to convert each array element ( 1 ? arr[i] ? 100 ) into their respective textual representations and print the lowercase representation of the count of all possible pairs from the array whose sum is equal to the total count of vowels present in their textual representation. If the count exceeds 100 print “greater 100”. Note: For the number 100, convert it to textual representation as hundred and not as one hundred.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}
Output: one
Explanation:
1 -> one -> o, e (2 vowels)
2 -> two -> o (1 vowel)
3 -> three -> e, e (2 vowels)
4 -> four -> o, u (2 vowels)
5 -> five – > i, e (2 vowels)
The total count of vowels in their textual representations = {2 + 1 + 2 + 2 + 2} = 9. Now from the given array, only a single unordered pair {4, 5} sums up to 9. Therefore, the count is 1. Hence, the required output is “one“.Input: arr[] = {7, 4, 2, }
Output: zero
Explanation:
7 -> seven -> e, e (2 vowels)
4 -> four -> o, u (2 vowels)
2 -> two -> o (1 vowel)
The total count of vowels in their textual representation = {2 + 2 + 1} = 5. Now from the given array, no pair exists which adds up to 5. Therefore, the answer is “zero“.
Approach: Follow the steps below to solve this problem:
- Store textual representation of each number from 0 to 100 in a Map.
- Traverse the array and for each array element, convert each digit to its textual form.
- Find the total number of vowels present in the textual forms and store it in a variable, say D.
- Now, generate all the pairs possible from the given array.
- Count all the pairs with sum D.
- If the count exceeds 100, “greater 100”. Otherwise, print its textual form.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check the string pair void string_pair( int n, vector< int >& nums) { unordered_map< int , string> words = { { 0, "zero" }, { 1, "one" }, { 2, "two" }, { 3, "three" }, { 4, "four" }, { 5, "five" }, { 6, "six" }, { 7, "seven" }, { 8, "eight" }, { 9, "nine" }, { 10, "ten" }, { 11, "eleven" }, { 12, "twelve" }, { 13, "thirteen" }, { 14, "fourteen" }, { 15, "fifteen" }, { 16, "sixteen" }, { 17, "seventeen" }, { 18, "eighteen" }, { 19, "nineteen" }, { 20, "twenty" }, { 21, "twentyone" }, { 22, "twentytwo" }, { 23, "twentythree" }, { 24, "twentyfour" }, { 25, "twentyfive" }, { 26, "twentysix" }, { 27, "twentyseven" }, { 28, "twentyeight" }, { 29, "twentynine" }, { 30, "thirty" }, { 31, "thirtyone" }, { 32, "thirtytwo" }, { 33, "thirtythree" }, { 34, "thirtyfour" }, { 35, "thirtyfive" }, { 36, "thirtysix" }, { 37, "thirtyseven" }, { 38, "thirtyeight" }, { 39, "thirtynine" }, { 40, "forty" }, { 41, "fortyone" }, { 42, "fortytwo" }, { 43, "fortythree" }, { 44, "fortyfour" }, { 45, "fortyfive" }, { 46, "fortysix" }, { 47, "fortyseven" }, { 48, "fortyeight" }, { 49, "fortynine" }, { 50, "fifty" }, { 51, "fiftyone" }, { 52, "fiftytwo" }, { 53, "fiftythree" }, { 54, "fiftyfour" }, { 55, "fiftyfive" }, { 56, "fiftysix" }, { 57, "fiftyseven" }, { 58, "fiftyeight" }, { 59, "fiftynine" }, { 60, "sixty" }, { 61, "sixtyone" }, { 62, "sixtytwo" }, { 63, "sixtythree" }, { 64, "sixtyfour" }, { 65, "sixtyfive" }, { 66, "sixtysix" }, { 67, "sixtyseven" }, { 68, "sixtyeight" }, { 69, "sixtynine" }, { 70, "seventy" }, { 71, "seventyone" }, { 72, "seventytwo" }, { 73, "seventythree" }, { 74, "seventyfour" }, { 75, "seventyfive" }, { 76, "seventysix" }, { 77, "seventyseven" }, { 78, "seventyeight" }, { 79, "seventynine" }, { 80, "eighty" }, { 81, "eightyone" }, { 82, "eightytwo" }, { 83, "eightythree" }, { 84, "eightyfour" }, { 85, "eightyfive" }, { 86, "eightysix" }, { 87, "eightyseven" }, { 88, "eightyeight" }, { 89, "eightynine" }, { 90, "ninety" }, { 91, "ninetyone" }, { 92, "ninetytwo" }, { 93, "ninetythree" }, { 94, "ninetyfour" }, { 95, "ninetyfive" }, { 96, "ninetysix" }, { 97, "ninetyseven" }, { 98, "ninetyeight" }, { 99, "ninetynine" }, { 100, "hundred" } }; // Temporary lists to store list of count vector< int > ls, ls1; int count = 0, c = 0; // Iterating through the numbers for ( auto i : nums) { // Stores the textual form of i string s = words[i]; for ( size_t a = 0; a < s.size(); a++) { // If it is vowel if (s[a] == 'a' || s[a] == 'e' || s[a] == 'i' || s[a] == 'o' || s[a] == 'u' ) { // Increment the count count++; } } // Append the count ls.push_back(count); count = 0; } // D = sum(count of vowels) int d = accumulate(ls.begin(), ls.end(), 0); for ( auto i : nums) { // To find the numbers less that or equal to d, // so as to find the pair sum if (i <= d) { // Append the numbers whose sum can be d ls1.push_back(i); } } // Stores all possible pairs in the // form of an object list of tuples vector<pair< int , int > > comb; for ( size_t i = 0; i < ls1.size(); i++) { for ( size_t j = i + 1; j < ls1.size(); j++) { comb.push_back(make_pair(ls1[i], ls1[j])); } } // Traverse all the pairs for ( auto i : comb) { // If sum is equal to d if (i.first + i.second == d) { // Increment count c++; } } // If count exceeds 100 if (c <= 100) { cout << words << endl; } // Otherwise else { cout << "greater 100" << endl; } } // Driver code int main() { // Given Length of string int n = 5; // Given array vector< int > arr = { 1, 2, 3, 4, 5 }; // Function Call string_pair(n, arr); return 0; } // Contributed by adityasha4x71 |
Java
import java.util.*; public class StringPair { public static void main(String[] args) { int n = 5 ; int [] arr = { 1 , 2 , 3 , 4 , 5 }; stringPair(n, arr); } public static void stringPair( int n, int [] nums) { Map<Integer, String> words = new HashMap<>(); initializeWords(words); List<Integer> ls = new ArrayList<>(); List<Integer> ls1 = new ArrayList<>(); int count = 0 ; for ( int i : nums) { String s = words.get(i); for ( int a = 0 ; a < s.length(); a++) { char ch = s.charAt(a); if (isVowel(ch)) { count++; } } ls.add(count); count = 0 ; } int d = ls.stream().mapToInt(Integer::intValue).sum(); for ( int i : nums) { if (i <= d) { ls1.add(i); } } List<List<Integer> > comb = combinations(ls1, 2 ); int c = 0 ; for (List<Integer> pair : comb) { if (pair.get( 0 ) + pair.get( 1 ) == d) { c++; } } if (c == 1 ) { System.out.println( "one" ); } else { System.out.println( "greater 100" ); } } public static List<List<Integer> > combinations(List<Integer> arr, int k) { List<List<Integer> > result = new ArrayList<>(); combine(result, new ArrayList<>(), arr, 0 , k); return result; } private static void combine(List<List<Integer> > result, List<Integer> current, List<Integer> arr, int start, int k) { if (current.size() == k) { result.add( new ArrayList<>(current)); return ; } for ( int i = start; i < arr.size(); i++) { current.add(arr.get(i)); combine(result, current, arr, i + 1 , k); current.remove(current.size() - 1 ); } } private static boolean isVowel( char ch) { return "aeiou" .indexOf(ch) != - 1 ; } private static void initializeWords(Map<Integer, String> words) { for ( int i = 0 ; i <= 100 ; i++) { words.put(i, getWord(i)); } } private static String getWord( int num) { if (num == 1 ) { return "one" ; } else if (num == 2 ) { return "two" ; } // Add similar logic for other numbers return "" ; } } |
Python3
# Python3 program for the above approach # Import combinations from itertools import combinations # Function to check the string pair def string_pair(n, nums): words = { 0 : 'zero' , 1 : 'one' , 2 : 'two' , 3 : 'three' , 4 : 'four' , 5 : 'five' , 6 : 'six' , 7 : 'seven' , 8 : 'eight' , 9 : 'nine' , 10 : 'ten' , 11 : 'eleven' , 12 : 'twelve' , 13 : 'thirteen' , 14 : 'fourteen' , 15 : 'fifteen' , 16 : 'sixteen' , 17 : 'seventeen' , 18 : 'eighteen' , 19 : 'nineteen' , 20 : 'twenty' , 21 : 'twentyone' , 22 : 'twentytwo' , 23 : 'twentythree' , 24 : 'twentyfour' , 25 : 'twentyfive' , 26 : 'twentysix' , 27 : 'twentyseven' , 28 : 'twentyeight' , 29 : 'twentynine' , 30 : 'thirty' , 31 : 'thirtyone' , 32 : 'thirtytwo' , 33 : 'thirtythree' , 34 : 'thirtyfour' , 35 : 'thirtyfive' , 36 : 'thirtysix' , 37 : 'thirtyseven' , 38 : 'thirtyeight' , 39 : 'thirtynine' , 40 : 'forty' , 41 : 'fortyone' , 42 : 'fortytwo' , 43 : 'fortythree' , 44 : 'fortyfour' , 45 : 'fortyfive' , 46 : 'fortysix' , 47 : 'fortyseven' , 48 : 'fortyeight' , 49 : 'fortynine' , 50 : 'fifty' , 51 : 'fiftyone' , 52 : 'fiftytwo' , 53 : 'fiftythree' , 54 : 'fiftyfour' , 55 : 'fiftyfive' , 56 : 'fiftysix' , 57 : 'fiftyseven' , 58 : 'fiftyeight' , 59 : 'fiftynine' , 60 : 'sixty' , 61 : 'sixtyone' , 62 : 'sixtytwo' , 63 : 'sixtythree' , 64 : 'sixtyfour' , 65 : 'sixtyfive' , 66 : 'sixtysix' , 67 : 'sixtyseven' , 68 : 'sixtyeight' , 69 : 'sixtynine' , 70 : 'seventy' , 71 : 'seventyone' , 72 : 'seventytwo' , 73 : 'seventythree' , 74 : 'seventyfour' , 75 : 'seventyfive' , 76 : 'seventysix' , 77 : 'seventyseven' , 78 : 'seventyeight' , 79 : 'seventynine' , 80 : 'eighty' , 81 : 'eightyone' , 82 : 'eightytwo' , 83 : 'eightythree' , 84 : 'eightyfour' , 85 : 'eightyfive' , 86 : 'eightysix' , 87 : 'eightyseven' , 88 : 'eightyeight' , 89 : 'eightynine' , 90 : 'ninety' , 91 : 'ninetyone' , 92 : 'ninetytwo' , 93 : 'ninetythree' , 94 : 'ninetyfour' , 95 : 'ninetyfive' , 96 : 'ninetysix' , 97 : 'ninetyseven' , 98 : 'ninetyeight' , 99 : 'ninetynine' , 100 : 'hundred' } # Map the string into list of integers nums = list ( map ( int , nums)) # Temporary lists to store list of count ls, ls1 = [], [] count, c = 0 , 0 # Iterating through the numbers for i in nums: # Stores the textual form of i s = words[i] for a in range ( len (s)): vo = [ 'a' , 'e' , 'i' , 'o' , 'u' ] # If it is vowel if s[a] in vo: # Increment the count count + = 1 # Append the count ls.append(count) count = 0 # D = sum(count of vowels) d = sum (ls) for i in nums: # To find the numbers less # that or equal to d, # so as to find the pair sum if i < = d: # Append the numbers # whose sum can be d ls1.append(i) # Stores all possible pairs in the # form of an object list of tuples comb = combinations(ls1, 2 ) # Traverse all the pairs for i in list (comb): # If sum is equal to d if sum (i) = = d: # Increment count c + = 1 # If count exceeds 100 if c < = 100 : print (words) # Otherwise else : print ( "greater 100" ) # Driver Code if __name__ = = '__main__' : # Given Length of string n = 5 # Given array arr = [ 1 , 2 , 3 , 4 , 5 ] # Function Call string_pair(n, arr) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { // Function to check the string pair static void StringPair( int n, List< int > nums) { // Dictionary to store textual representations of numbers Dictionary< int , string > words = new Dictionary< int , string > { { 0, "zero" }, { 1, "one" }, { 2, "two" }, { 3, "three" }, { 4, "four" }, { 5, "five" }, { 6, "six" }, { 7, "seven" }, { 8, "eight" }, { 9, "nine" }, { 10, "ten" }, { 11, "eleven" }, { 12, "twelve" }, { 13, "thirteen" }, { 14, "fourteen" }, { 15, "fifteen" }, { 16, "sixteen" }, { 17, "seventeen" }, { 18, "eighteen" }, { 19, "nineteen" }, { 20, "twenty" }, { 21, "twentyone" }, { 22, "twentytwo" }, { 23, "twentythree" }, { 24, "twentyfour" }, { 25, "twentyfive" }, { 26, "twentysix" }, { 27, "twentyseven" }, { 28, "twentyeight" }, { 29, "twentynine" }, { 30, "thirty" }, { 31, "thirtyone" }, { 32, "thirtytwo" }, { 33, "thirtythree" }, { 34, "thirtyfour" }, { 35, "thirtyfive" }, { 36, "thirtysix" }, { 37, "thirtyseven" }, { 38, "thirtyeight" }, { 39, "thirtynine" }, { 40, "forty" }, { 41, "fortyone" }, { 42, "fortytwo" }, { 43, "fortythree" }, { 44, "fortyfour" }, { 45, "fortyfive" }, { 46, "fortysix" }, { 47, "fortyseven" }, { 48, "fortyeight" }, { 49, "fortynine" }, { 50, "fifty" }, { 51, "fiftyone" }, { 52, "fiftytwo" }, { 53, "fiftythree" }, { 54, "fiftyfour" }, { 55, "fiftyfive" }, { 56, "fiftysix" }, { 57, "fiftyseven" }, { 58, "fiftyeight" }, { 59, "fiftynine" }, { 60, "sixty" }, { 61, "sixtyone" }, { 62, "sixtytwo" }, { 63, "sixtythree" }, { 64, "sixtyfour" }, { 65, "sixtyfive" }, { 66, "sixtysix" }, { 67, "sixtyseven" }, { 68, "sixtyeight" }, { 69, "sixtynine" }, { 70, "seventy" }, { 71, "seventyone" }, { 72, "seventytwo" }, { 73, "seventythree" }, { 74, "seventyfour" }, { 75, "seventyfive" }, { 76, "seventysix" }, { 77, "seventyseven" }, { 78, "seventyeight" }, { 79, "seventynine" }, { 80, "eighty" }, { 81, "eightyone" }, { 82, "eightytwo" }, { 83, "eightythree" }, { 84, "eightyfour" }, { 85, "eightyfive" }, { 86, "eightysix" }, { 87, "eightyseven" }, { 88, "eightyeight" }, { 89, "eightynine" }, { 90, "ninety" }, { 91, "ninetyone" }, { 92, "ninetytwo" }, { 93, "ninetythree" }, { 94, "ninetyfour" }, { 95, "ninetyfive" }, { 96, "ninetysix" }, { 97, "ninetyseven" }, { 98, "ninetyeight" }, { 99, "ninetynine" }, { 100, "hundred" } }; // Temporary lists to store list of count List< int > ls = new List< int >(); List< int > ls1 = new List< int >(); int count = 0, c = 0; // Iterating through the numbers foreach ( var i in nums) { // Stores the textual form of i string s = words[i]; for ( int a = 0; a < s.Length; a++) { // If it is vowel if (s[a] == 'a' || s[a] == 'e' || s[a] == 'i' || s[a] == 'o' || s[a] == 'u' ) { // Increment the count count++; } } // Append the count ls.Add(count); count = 0; } // D = sum(count of vowels) int d = ls.Sum(); foreach ( var i in nums) { // To find the numbers less that or equal to d, // so as to find the pair sum if (i <= d) { // Append the numbers whose sum can be d ls1.Add(i); } } // Stores all possible pairs in the // form of an object list of tuples List<Tuple< int , int >> comb = new List<Tuple< int , int >>(); for ( int i = 0; i < ls1.Count; i++) { for ( int j = i + 1; j < ls1.Count; j++) { comb.Add( new Tuple< int , int >(ls1[i], ls1[j])); } } // Traverse all the pairs foreach ( var i in comb) { // If sum is equal to d if (i.Item1 + i.Item2 == d) { // Increment count c++; } } // If count exceeds 100 if (c <= 100) { Console.WriteLine(words); } // Otherwise else { Console.WriteLine( "greater 100" ); } } // Driver code static void Main() { // Given Length of string int n = 5; // Given array List< int > arr = new List< int > { 1, 2, 3, 4, 5 }; // Function Call StringPair(n, arr); } } |
Javascript
// Function to check the string pair function stringPair(n, nums) { // Dictionary to map numbers to their textual form const words = { 0: 'zero' , 1: 'one' , 2: 'two' , 3: 'three' , 4: 'four' , 5: 'five' , 6: 'six' , 7: 'seven' , 8: 'eight' , 9: 'nine' , 10: 'ten' , 11: 'eleven' , 12: 'twelve' , 13: 'thirteen' , 14: 'fourteen' , 15: 'fifteen' , 16: 'sixteen' , 17: 'seventeen' , 18: 'eighteen' , 19: 'nineteen' , 20: 'twenty' , 21: 'twentyone' , 22: 'twentytwo' , 23: 'twentythree' , 24: 'twentyfour' , 25: 'twentyfive' , 26: 'twentysix' , 27: 'twentyseven' , 28: 'twentyeight' , 29: 'twentynine' , 30: 'thirty' , 31: 'thirtyone' , 32: 'thirtytwo' , 33: 'thirtythree' , 34: 'thirtyfour' , 35: 'thirtyfive' , 36: 'thirtysix' , 37: 'thirtyseven' , 38: 'thirtyeight' , 39: 'thirtynine' , 40: 'forty' , 41: 'fortyone' , 42: 'fortytwo' , 43: 'fortythree' , 44: 'fortyfour' , 45: 'fortyfive' , 46: 'fortysix' , 47: 'fortyseven' , 48: 'fortyeight' , 49: 'fortynine' , 50: 'fifty' , 51: 'fiftyone' , 52: 'fiftytwo' , 53: 'fiftythree' , 54: 'fiftyfour' , 55: 'fiftyfive' , 56: 'fiftysix' , 57: 'fiftyseven' , 58: 'fiftyeight' , 59: 'fiftynine' , 60: 'sixty' , 61: 'sixtyone' , 62: 'sixtytwo' , 63: 'sixtythree' , 64: 'sixtyfour' , 65: 'sixtyfive' , 66: 'sixtysix' , 67: 'sixtyseven' , 68: 'sixtyeight' , 69: 'sixtynine' , 70: 'seventy' , 71: 'seventyone' , 72: 'seventytwo' , 73: 'seventythree' , 74: 'seventyfour' , 75: 'seventyfive' , 76: 'seventysix' , 77: 'seventyseven' , 78: 'seventyeight' , 79: 'seventynine' , 80: 'eighty' , 81: 'eightyone' , 82: 'eightytwo' , 83: 'eightythree' , 84: 'eightyfour' , 85: 'eightyfive' , 86: 'eightysix' , 87: 'eightyseven' , 88: 'eightyeight' , 89: 'eightynine' , 90: 'ninety' , 91: 'ninetyone' , 92: 'ninetytwo' , 93: 'ninetythree' , 94: 'ninetyfour' , 95: 'ninetyfive' , 96: 'ninetysix' , 97: 'ninetyseven' , 98: 'ninetyeight' , 99: 'ninetynine' , 100: 'hundred' }; // Map the string into a list of integers nums = nums.map(Number); // Temporary arrays to store the count let ls = []; let ls1 = []; let count = 0; // Iterating through the numbers for (let i of nums) { // Stores the textual form of i const s = words[i]; // Count the number of vowels in the textual form for (let a = 0; a < s.length; a++) { const vo = [ 'a' , 'e' , 'i' , 'o' , 'u' ]; // If it is a vowel, increment the count if (vo.includes(s[a])) { count++; } } // Append the count ls.push(count); count = 0; } // Calculate D = sum(count of vowels) const d = ls.reduce((acc, val) => acc + val, 0); // Find numbers less than or equal to d for (let i of nums) { // Append the numbers whose sum can be d if (i <= d) { ls1.push(i); } } // Stores all possible pairs in the form of an array of tuples const comb = combinations(ls1, 2); // Count the pairs whose sum is equal to d let c = 0; for (let i of comb) { if (i[0] + i[1] === d) { c++; } } // Output based on the count if (c <= 100) { console.log(words); } else { console.log( "greater 100" ); } } // Function to generate combinations of an array function combinations(arr, k) { const result = []; function combine(current, start) { if (current.length === k) { result.push([...current]); return ; } for (let i = start; i < arr.length; i++) { current.push(arr[i]); combine(current, i + 1); current.pop(); } } combine([], 0); return result; } // Driver Code const n = 5; const arr = [1, 2, 3, 4, 5]; // Function Call stringPair(n, arr); |
one
Time Complexity: O(N2)
Auxiliary Space: O(N2)