Given a string str of uppercase alphabets and numbers, the task is to find the number of matchsticks required to represent it.
Examples:
Input: str = “ABC2”
Output: 22
Explanation:
6 sticks are required to represent A,
7 sticks are required to represent B,
4 sticks are required to represent C,
5 sticks are required to represent 2.
Therefore the total number of matchsticks required is 6 + 7 + 4 + 5 = 22.
Input: str = “GEEKSFORGEEKS”
Output: 66
Explanation:
6 sticks are required to represent G,
5 sticks are required to represent E,
4 sticks are required to represent K,
5 sticks are required to represent S,
4 sticks are required to represent F,
6 sticks are required to represent O,
6 sticks are required to represent R.
Therefore the total number of matchsticks required is 6 + 5 + 5 + 4 + 5 + 4 + 6 + 6 + 6 + 5 + 5 + 4 + 5 = 17.
Approach:
- The idea is to store the count of matchstick required to represent a particular alphabet and number as shown in above image.
- Traverse the given string str and add the count of matchstick required for each character.
Below is the implementation of the above approach:
C++
// C++ implementation of the// above approach#include <bits/stdc++.h>using namespace std;// stick[] stores the count// of matchsticks required to// represent the alphabetsint sticks[] = { 6, 7, 4, 6, 5, 4, 6, 5, 2, 4, 4, 3, 6, 6, 6, 5, 7, 6, 5, 3, 5, 4, 6, 4, 3, 4 };// number[] stores the count// of matchsticks required to// represent the numeralsint number[] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };// Function that return the count of// sticks required to represent// the given stringint countSticks(string str){ int cnt = 0; // For every char of the given // string for (int i = 0; str[i]; i++) { char ch = str[i]; // Add the count of sticks // required to represent the // current character if (ch >= 'A' && ch <= 'Z') { cnt += sticks[ch - 'A']; } else { cnt += number[ch - '0']; } } return cnt;}// Driver codeint main(){ string str = "GEEKSFORGEEKS"; // Function call to find the // count of matchsticks cout << countSticks(str); return 0;} |
Java
// Java implementation of the above approachclass GFG { // stick[] stores the count // of matchsticks required to // represent the alphabets static int sticks[] = { 6, 7, 4, 6, 5, 4, 6, 5, 2, 4, 4, 3, 6, 6, 6, 5, 7, 6, 5, 3, 5, 4, 6, 4, 3, 4 }; // number[] stores the count // of matchsticks required to // represent the numerals static int number[] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 }; // Function that return the count of // sticks required to represent // the given string static int countSticks(String str) { int cnt = 0; // For every char of the given // string for (int i = 0; i < str.length(); i++) { char ch = str.charAt(i); // Add the count of sticks // required to represent the // current character if (ch >= 'A' && ch <= 'Z') { cnt += sticks[ch - 'A']; } else { cnt += number[ch - '0']; } } return cnt; } // Driver code public static void main (String[] args) { String str = "GEEKSFORGEEKS"; // Function call to find the // count of matchsticks System.out.println(countSticks(str)); }}// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the above approach # stick[] stores the count # of matchsticks required to # represent the alphabets sticks = [ 6, 7, 4, 6, 5, 4, 6, 5, 2, 4, 4, 3, 6, 6, 6, 5, 7, 6, 5, 3, 5, 4, 6, 4, 3, 4 ]; # number[] stores the count # of matchsticks required to # represent the numerals number = [ 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]; # Function that return the count of # sticks required to represent # the given string def countSticks(string) : cnt = 0; # For every char of the given # string for i in range(len(string)) : ch = string[i]; # Add the count of sticks # required to represent the # current character if (ch >= 'A' and ch <= 'Z') : cnt += sticks[ord(ch) - ord('A')]; else : cnt += number[ord(ch) - ord('0')]; return cnt; # Driver code if __name__ == "__main__" : string = "GEEKSFORGEEKS"; # Function call to find the # count of matchsticks print(countSticks(string)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the above approachusing System;class GFG{ // stick[] stores the count // of matchsticks required to // represent the alphabets static int []sticks = { 6, 7, 4, 6, 5, 4, 6, 5, 2, 4, 4, 3, 6, 6, 6, 5, 7, 6, 5, 3, 5, 4, 6, 4, 3, 4 }; // number[] stores the count // of matchsticks required to // represent the numerals static int []number = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 }; // Function that return the count of // sticks required to represent // the given string static int countSticks(string str) { int cnt = 0; // For every char of the given // string for (int i = 0; i < str.Length; i++) { char ch = str[i]; // Add the count of sticks // required to represent the // current character if (ch >= 'A' && ch <= 'Z') { cnt += sticks[ch - 'A']; } else { cnt += number[ch - '0']; } } return cnt; } // Driver code public static void Main() { string str = "GEEKSFORGEEKS"; // Function call to find the // count of matchsticks Console.WriteLine(countSticks(str)); }}// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript implementation of the// above approach// stick[] stores the count// of matchsticks required to// represent the alphabetsvar sticks = [ 6, 7, 4, 6, 5, 4, 6, 5, 2, 4, 4, 3, 6, 6, 6, 5, 7, 6, 5, 3, 5, 4, 6, 4, 3, 4 ]// number[] stores the count// of matchsticks required to// represent the numeralsvar number = [ 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]; // Function that return the count of// sticks required to represent// the given stringfunction countSticks(str){ var cnt = 0; // For every char of the given // string for (var i = 0; str[i]; i++) { var ch = str[i]; // Add the count of sticks // required to represent the // current character if (ch >= 'A' && ch <= 'Z') { cnt += sticks[ch.charCodeAt(0) - 'A'.charCodeAt(0)]; } else { cnt += number[ch.charCodeAt(0) - '0'.charCodeAt(0)]; } } return cnt;} // Driver Code // Given arrayvar str = "GEEKSFORGEEKS";// Function Calldocument.write(countSticks(str));// This code is contributed by ShubhamSingh10</script> |
Output:
66
Time Complexity: O(N), where N is the length of given string.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
