Question Name:INTELLIGENT GIRL

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main()
{
    string s;
    cin>>s;
    ll l=s.length();
    ll a[l],k=0;
    for(ll i=(l-1);i>=0;i--)
    {
        if(s[i]%2==0)
        {
            k+=1;
            a[i]=k;
        }
        else
        {
            a[i]=k;
        }
    }
    for(ll i=0;i<l;i++)
    {
       cout<<a[i]<<" "; 
    }
    
    return 0;
}

• Problem Description
  Soumika has a string S and its starting index is 1. The string S consists of characters from 19. As she is very intelligent, she wants to test his brother Vinay Tendulkar.
  
  She asked her brother Vinay Tendulkar to count the number of even numbered characters ( i.e 2,4,6,8 ) for every index
  (1<=i<=|S|). For an index i, the result should be calculated from i to the end of the string. As Vinay doesn’t know about programming, he wants you to help him find the solution.
  
  Input:
  First line contains a string S.
  
  Output:
  Print |S| space-separated integers,the result of every index.
  
  Constraints:
  
  1<= |S| <= 10^4
• Test Case 1
  Input (stdin)574674546
  Expected Output5 5 5 4 3 3 2 2 1
• Test Case 2
  Input (stdin) 54566987543
  Expected Output 5 5 4 4 3 2 2 1 1 1 0

Soumika asks her brother Vinay Tendulkar to count the number of even digits (characters) in a string for every index from the current position to the end of the string. The string consists of digits ranging from '1' to '9', and for each position in the string, the task is to calculate how many even digits (2, 4, 6, 8) appear from that position up to the last character.

The problem asks for a solution that can handle up to 10,000 characters, so efficiency is key.

Input and Output:

Input:

• A single string $S$ consisting of characters from '1' to '9'.

Output:

• Print $|S|$ space-separated integers. For each index $i$ (from 1 to $|S|$), the result is the number of even digits from the $i$-th position to the end of the string.

Example:

Test Case 1:

Input:

574674546

Output:

5 5 5 4 3 3 2 2 1

Here, for index 1 (i.e., starting from the first digit 5), there are 5 even digits (4, 6, 4, 4, 6) from index 1 to the end. For index 2, there are still 5 even digits, and so on.

Test Case 2:

Input:

54566987543

Output:

5 5 4 4 3 2 2 1 1 1 0

In this example, for index 1, there are 5 even digits (4, 6, 6, 8, 4) from index 1 to the end.

Solution Breakdown:

1. Understanding the Problem:

   • For each index in the string, we need to count the number of even digits from that index to the end.
   • The characters '2', '4', '6', and '8' are considered even digits, and all others ('1', '3', '5', '7', '9') are odd.
   • We need to output an array where each element corresponds to the count of even digits starting from that index till the end.

2. Efficiency Consideration:

   • A brute force approach where we count the even digits for each index by iterating over the rest of the string would be inefficient (leading to a time complexity of $O(N^2)$).
   • Instead, we can solve this problem efficiently in linear time using a right-to-left traversal of the string and keeping track of even digits as we go.

3. Optimized Approach:

• Traverse the string from right to left. For each character, check if it's an even digit. If it is, increment a counter (k).
• Store the count of even digits from the current index to the end in an array.
• This approach ensures that we only need to make a single pass through the string, making the time complexity $O(N)$, where $N$ is the length of the string.

Explanation of the Code:

1. Input Handling:

   • The input string s is read, and its length l is determined.

2. Array a[] Initialization:

   • An array a[] of size l is created to store the results. Each element a[i] will contain the number of even digits from index i to the end of the string.

3. Right-to-Left Traversal:

   • The string is traversed from right to left (starting from the last character). This allows us to keep a running count of the even digits seen so far.

   • For each character:

     • If it's an even digit (determined by checking if the character's ASCII value modulo 2 is 0), the counter k is incremented.
     • The value of k (the number of even digits from the current index to the end) is stored in the array a[].

   • If the character is not even, we simply store the current value of k in a[].

4. Output:

   • After processing the entire string, the array a[] is printed, with each value representing the count of even digits starting from that index to the end of the string.

Key Concepts:

• Right-to-Left Traversal: By iterating from the end of the string to the beginning, we can efficiently calculate the number of even digits for each position without having to recheck the entire string multiple times.

• Character to Integer Conversion: The expression s[i] % 2 == 0 works because the characters in the string are ASCII values, and when we check for even digits (like '2', '4', '6', '8'), they correspond to even ASCII values.

Time and Space Complexity:

• Time Complexity: $O(N)$, where $N$ is the length of the string. We only traverse the string once.

• Space Complexity: $O(N)$ for the array a[] which stores the result for each index.

Example Walkthrough:

For the input string "574674546":

1. Start at the last character ('6'), which is even. So, k = 1, and a[8] = 1.
2. Move to the previous character ('4'), which is also even. Now k = 2, and a[7] = 2.
3. Continue this process for each character, updating k when an even digit is found and storing the current value of k in the corresponding position in a[].