Horje
Check whether the given String is good for any ascending Array or not

Given a string S of length N. Consider any ascending array A[] such that each A[i] > 0 for all (1 <= i <= N) and some conditions, the task is to output YES/NO, by checking that the above-given conditions are true for all possible ascending A[]’s or not with given S.

  • Sum up all the elements of A[] at each index i, where S[i] = 1 in a variable let’s say X.
  • Sum up all the elements of A[] at each index i, where S[i] = 0 in a variable let’s say Y.
  • Then |X – Y| must be less than or equal to Max(A[]).

Any array is said to be ascending, If all element except the last is less than or equal to its next element. Formally, A[] = {A1 <= A2 <= A3 <= A4 . . . . <= A5}.

Examples: All the below arrays are ascending arrays.

  • A[] = {1, 2, 3, 5}
  • A[] = {5, 6, 7, 8}
  • A[] = {2, 2, 2, 2}
  • A[] = {3, 6, 8, 8}

Examples:

Input: N = 4, S = 1010

Output: YES

Explanation: Let us check the given S for multiple ascending arrays:

  • A[] = {2, 5, 8, 9}
    • S contains 1s at index 1 and 3, Then X = A[1] + A[3] = 2+8 = 10
    • S contains 0s at index 2 and 4, Then X = A[2] + A[4] = 9+5 =14
    • |X – Y| = |10 – 14| = 4.
    • Max element of A[] = 9
    • It can be checked that (|X-Y| = 4) <= 9. Thus, A[] satisfies that given condition with given S.
  • A[] = {2, 2, 2, 2}
    • S contains 1s at index 1 and 3, Then X = A[1] + A[3] = 2+2 = 4
    • S contains 0s at index 2 and 4, Then X = A[2] + A[4] = 2+2 = 4
    • |X – Y| = |4 – 4| = 0.
    • Max element of A[] = 9
    • It can be checked that (|X-Y| = 0) <= 9. Thus, A[] satisfies that given condition with given S.

For any possible ascending array A[] of length 4. The given conditions will always be true. Therefore, output is YES.

Input: N = 5, S = 00001

Output: NO

Explanation: S doesn’t follow all the given conditions with all possible ascending A[]’s. One such A[] is: {2, 2, 2, 2, 2}. For this A[], X and Y will be 2 and 8 respectively and then |X – Y| = |2 – 8| = 6 and Max(A[]) = 2. Thus, the condition (|X – Y| = 6) <= 2 fails. Therefore, output is NO.

Approach: Implement the idea below to solve the problem

This is an observation-based problem. Reverse S and start counting 1s. Then go with the approach of balanced parenthesis. If multiple 1 or 0 are found and the count of 1s goes less than -1 or greater than 1, Then it is not possible all cases else it is possible.

Steps were taken to solve the problem:

  • Create a boolean variable, let say Flag and mark it initially True.
  • Declare a variable let say Count to store the frequency of 1s.
  • Run a loop from back of the String and follow below steps under the scope of loop:
    • If (current character == 1)
      • Decrement Count
    • Else
      • Increment Count
  • If (Count < -1 || Count > 1)
    • Flag = false
    • Break the loop
  • If (Flag), then output YES.

Code to implement the approach:

C++

#include <iostream>
#include <string>
 
// Declare the function prototype
void Satisfies_all_A(int N, std::string S);
 
// Driver Function
int main() {
    // Inputs
    int N = 5;
    std::string S = "00001";
 
    // Function call
    Satisfies_all_A(N, S);
 
    return 0;
}
 
// Method to check that given S satisfies
// all possible ascending arrays A[]
void Satisfies_all_A(int N, std::string S) {
    // Flag
    bool flag = true;
 
    // Variable to count 1s
    int count = 0;
 
    // Loop for traversing S from back
    // and counting 1s
    for (int i = N - 1; i >= 0; i--) {
 
        if (S[i] == '1')
            count--;
        else
            count++;
 
        // If discussed condition breaches
        // Then marking flag false
        // and breaking the loop
        if (count < -1 || count > 1) {
            flag = false;
            std::cout << "NO" << std::endl;
            break;
        }
    }
 
    // Printing YES if count of 1s are
    // appropriate
    if (flag)
        std::cout << "YES" << std::endl;
}

Java

// Java code to implement the approach
import java.util.*;
 
// Driver class
public class GFG {
    // Driver Function
    public static void main(String[] args)
    {
        // Inputs
        int N = 5;
        String S = "00001";
 
        // Function_call
        Satisfies_all_A(N, S);
    }
 
    // Method to check that given S satisfies
    // all possible ascending arrays A[]
    public static void Satisfies_all_A(int N, String S)
    {
        // Flag
        boolean flag = true;
 
        // Variable to count 1s
        int count = 0;
 
        // Loop for traversing S from back
        // and counting 1s
        for (int i = N - 1; i >= 0; i--) {
 
            if (S.charAt(i) == '1')
                count--;
            else
                count++;
 
            // If discussed condition breaches
            // Then marking flag false
            // and breaking the loop
            if (count < -1 || count > 1) {
                flag = false;
                System.out.println("NO");
                break;
            }
        }
 
        // Printing YES if count of 1s are
        // appropriate
        if (flag)
            System.out.println("YES");
    }
}

Python3

# Method to check that given S satisfies
# all possible ascending arrays A[]
def satisfies_all_A(N, S):
    # Flag
    flag = True
 
    # Variable to count 1s
    count = 0
 
    # Loop for traversing S from back
    # and counting 1s
    for i in range(N - 1, -1, -1):
        if S[i] == '1':
            count -= 1
        else:
            count += 1
 
        # If discussed condition breaches
        # Then marking flag false
        # and breaking the loop
        if count < -1 or count > 1:
            flag = False
            print("NO")
            break
 
    # Printing YES if count of 1s are
    # appropriate
    if flag:
        print("YES")
 
# Driver code
if __name__ == "__main__":
    # Inputs
    N = 5
    S = "00001"
 
    # Function call
    satisfies_all_A(N, S)

C#

using System;
 
public class GFG {
    // Main Method
    public static void Main(string[] args)
    {
        // Inputs
        int N = 5;
        string S = "00001";
 
        // Function call
        SatisfiesAllA(N, S);
    }
 
    // Method to check that given S satisfies
    // all possible ascending arrays A[]
    public static void SatisfiesAllA(int N, string S)
    {
        // Flag
        bool flag = true;
 
        // Variable to count 1s
        int count = 0;
 
        // Loop for traversing S from back
        // and counting 1s
        for (int i = N - 1; i >= 0; i--) {
            if (S[i] == '1')
                count--;
            else
                count++;
 
            // If discussed condition breaches
            // Then marking flag false
            // and breaking the loop
            if (count < -1 || count > 1) {
                flag = false;
                Console.WriteLine("NO");
                break;
            }
        }
 
        // Printing YES if count of 1s are
        // appropriate
        if (flag)
            Console.WriteLine("YES");
    }
}

Javascript

// Function to check that given S satisfies
// all possible ascending arrays A[]
function satisfiesAllA(N, S) {
    // Flag
    let flag = true;
 
    // Variable to count 1s
    let count = 0;
 
    // Loop for traversing S from back
    // and counting 1s
    for (let i = N - 1; i >= 0; i--) {
        if (S[i] === '1') {
            count -= 1;
        } else {
            count += 1;
        }
 
        // If discussed condition breaches
        // Then marking flag false
        // and breaking the loop
        if (count < -1 || count > 1) {
            flag = false;
            console.log("NO");
            break;
        }
    }
 
    // Printing YES if count of 1s are
    // appropriate
    if (flag) {
        console.log("YES");
    }
}
 
// Driver code
// Inputs
const N = 5;
const S = "00001";
 
// Function call
satisfiesAllA(N, S);

Output

NO

Time Complexity: O(N)
Auxiliary space: O(1)


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
DSA Crash Course | Revision Checklist with Interview Guide DSA Crash Course | Revision Checklist with Interview Guide
What is the best way to inject Dependency in Java? What is the best way to inject Dependency in Java?
When is Doubly Linked List more Efficient than Singly Linked List? When is Doubly Linked List more Efficient than Singly Linked List?
Last node at which Frog is standing after t seconds Last node at which Frog is standing after t seconds
Maximum Sum Level Except Triangular Number in Binary Tree Maximum Sum Level Except Triangular Number in Binary Tree

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje