Given an array arr[] consisting of N positive integers, the task is to count subarrays consisting of single-digit elements only.
Examples:
Input: arr[] = {0, 1, 14, 2, 5}
Output: 6
Explanation: All subarrays made of only single digit numbers are {{0}, {1}, {2}, {5}, {0, 1}, {2, 5}}. Therefore, the total count of subarrays is 6.Input: arr[] ={12, 5, 14, 17}
Output: 1
Explanation: All subarrays made of only single digit numbers are {5}.
Therefore, the total count of subarrays is 1.
Naive Approach: The simplest approach is to traverse the array and generate all possible subarrays. For each subarray, check if all integers in it are single-digit integers or not.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to find the size of each block of contiguous single-digit integers and increment the count by total subarrays of that length. Follow the steps below to solve the problem:
- Initialize a variable, say res = 0 and c = 0, to store the total count of subarrays and the total count of single-digit integers in a subarray.
- Traverse the array and perform the following operations:
- If arr[i] < 10, increment the count of c by one and count of res by c.
- Otherwise, assign c = 0.
- Finally, print the total count of single-digit integer subarrays.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count of subarrays made// up of single digit integers onlyint singleDigitSubarrayCount(int arr[], int N){ // Stores count of subarrays int res = 0; // Stores the count of consecutive // single digit numbers in the array int count = 0; // Traverse the array for (int i = 0; i < N; i++) { if (arr[i] <= 9) { // Increment size of block by 1 count++; // Increment res by count res += count; } else { // Assign count = 0 count = 0; } } cout << res;}// Driver Codeint main(){ // Given array int arr[] = { 0, 1, 14, 2, 5 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); singleDigitSubarrayCount(arr, N); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to count of subarrays made// up of single digit integers onlystatic void singleDigitSubarrayCount(int arr[], int N){ // Stores count of subarrays int res = 0; // Stores the count of consecutive // single digit numbers in the array int count = 0; // Traverse the array for (int i = 0; i < N; i++) { if (arr[i] <= 9) { // Increment size of block by 1 count++; // Increment res by count res += count; } else { // Assign count = 0 count = 0; } } System.out.print(res);}// Driver Codepublic static void main(String[] args){ // Given array int arr[] = { 0, 1, 14, 2, 5 }; // Size of the array int N = arr.length; singleDigitSubarrayCount(arr, N);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function to count of subarrays made# up of single digit integers onlydef singleDigitSubarrayCount(arr, N): # Stores count of subarrays res = 0 # Stores the count of consecutive # single digit numbers in the array count = 0 # Traverse the array for i in range(N): if (arr[i] <= 9): # Increment size of block by 1 count += 1 # Increment res by count res += count else: # Assign count = 0 count = 0 print (res)# Driver Codeif __name__ == '__main__': # Given array arr = [0, 1, 14, 2, 5] # Size of the array N = len(arr) singleDigitSubarrayCount(arr, N) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG{// Function to count of subarrays made// up of single digit integers onlystatic void singleDigitSubarrayCount(int[] arr, int N){ // Stores count of subarrays int res = 0; // Stores the count of consecutive // single digit numbers in the array int count = 0; // Traverse the array for (int i = 0; i < N; i++) { if (arr[i] <= 9) { // Increment size of block by 1 count++; // Increment res by count res += count; } else { // Assign count = 0 count = 0; } } Console.Write(res);}// Driver Codepublic static void Main(string[] args){ // Given array int[] arr = { 0, 1, 14, 2, 5 }; // Size of the array int N = arr.Length; singleDigitSubarrayCount(arr, N);}}// This code is contributed by sanjoy_62. |
Javascript
<script>// Javascript program for the above approach// Function to count of subarrays made// up of single digit integers onlyfunction singleDigitSubarrayCount(arr, N){ // Stores count of subarrays let res = 0; // Stores the count of consecutive // single digit numbers in the array let count = 0; // Traverse the array for(let i = 0; i < N; i++) { if (arr[i] <= 9) { // Increment size of block by 1 count++; // Increment res by count res += count; } else { // Assign count = 0 count = 0; } } document.write(res);}// Driver Code// Given arraylet arr = [ 0, 1, 14, 2, 5 ];// Size of the arraylet N = arr.length;singleDigitSubarrayCount(arr, N);// This code is contributed by Manoj.</script> |
6
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach#2: Using nested loop
This approach is a brute-force solution. The code loops over all possible subarrays of the input array and checks if each subarray is made up of single-digit integers only. If it is, the count of such subarrays is incremented.
Algorithm
1. Initialize a variable count to 0.
2. Loop through the array using two nested loops. The outer loop iterates from 0 to n-1, where n is the length of the input array. The inner loop iterates from the current outer loop index to n-1.
3. For each subarray formed by the outer and inner loop indices, check if it contains only single-digit integers. This is done using a nested loop that iterates through each element of the subarray and checks if it is a single-digit integer.
4. If the subarray is made up of only single-digit integers, increment the count variable.
5. After looping through all subarrays, return the count.
C++
#include <iostream>#include <vector>using namespace std;int count_single_digit_subarrays(const vector<int>& arr) { int n = arr.size(); int count = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { bool is_single_digit_subarray = true; for (int k = i; k <= j; k++) { if (arr[k] < 0 || arr[k] > 9) { is_single_digit_subarray = false; break; } } if (is_single_digit_subarray) { count++; } } } return count;}int main() { vector<int> arr1 = {0, 1, 14, 2, 5}; cout << count_single_digit_subarrays(arr1) << endl; vector<int> arr2 = {12, 5, 14, 17}; cout << count_single_digit_subarrays(arr2) << endl; return 0;} |
Java
import java.util.*;public class GFG { // Function to count the number of single-digit subarrays in the given vector public static int countSingleDigitSubarrays(List<Integer> arr) { int n = arr.size(); int count = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { boolean isSingleDigitSubarray = true; for (int k = i; k <= j; k++) { if (arr.get(k) < 0 || arr.get(k) > 9) { isSingleDigitSubarray = false; break; } } if (isSingleDigitSubarray) { count++; } } } return count; } // Driver Code public static void main(String[] args) { List<Integer> arr1 = Arrays.asList(0, 1, 14, 2, 5); System.out.println(countSingleDigitSubarrays(arr1)); List<Integer> arr2 = Arrays.asList(12, 5, 14, 17); System.out.println(countSingleDigitSubarrays(arr2)); }} |
Python3
def count_single_digit_subarrays(arr): n = len(arr) count = 0 for i in range(n): for j in range(i, n): is_single_digit_subarray = True for k in range(i, j+1): if arr[k] < 0 or arr[k] > 9: is_single_digit_subarray = False break if is_single_digit_subarray: count += 1 return countarr1 = [0, 1, 14, 2, 5]print(count_single_digit_subarrays(arr1)) arr2 = [12, 5, 14, 17]print(count_single_digit_subarrays(arr2)) |
6 1
Time Complexity: O(n^3), where n is the length of the input array. This is because the code uses three nested loops to iterate through all possible subarrays of the input array.
Auxiliary Space: O(1), as it only uses a constant amount of extra space to store the count variable. The input array is not modified, and no extra data structures are used.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
