Given a string S of size N, the duty is to test whether or not it’s attainable to partition the string S into two disjoint non-empty subsequences S1 and S2 such that sum(S1) × sum(S2) is odd and each character of S should be in both S2 and S1.
Examples:
Enter: S = “1122”
Output: Sure
Clarification: We partition the string into two subsequences .Let S1 be the underlined components and S2 be the opposite ones. sum(S1) × sum(S2) = 3 × 3 = 9.Enter: S = “135”
Output: No
Method: The issue could be solved primarily based on the next remark:
To make the product of two numbers odd, each numbers must be odd. So, the sum of S1 and S2 should be odd. That is solely attainable when every of them has odd variety of odd integers. If the string has even quantity (besides 0) of wierd digits then solely such a partition is posisble.
This satisfies that the sum of S may even be even and there will probably be atleast 2 odd numbers.
Observe the steps talked about beneath to implement the concept:
- Traverse by the string S.
- Verify if the sum is even and the variety of odd digits is at the least 2.
- If the situation is happy, the partition is feasible.
- In any other case, the partition just isn’t attainable.
Beneath is the implementation of the above strategy.
Java
|
|
Time Complexity: O(N)
Auxiliary Area: O(1)
Associated Articles:
