Given a positive integer N, the task is to find the minimum number of digits required to be removed to convert N to an odd number whose sum of digits is even. If it is impossible to do so, then print “Not Possible”.
Examples:
Input: N = 12345
Output: 1
Explanation:
Removing the digit 3 modifies N to 1245.
Since the sum of digits of N is 14 and N is odd, the required output is 1.Input: N = 222
Output: Not Possible
Approach: The idea is to use the fact that summation of even count of odd numbers results in an even number. Follow the steps below to solve the problem:
- Count total odd and even digits present in the integer N and store them in variables, say Odd and Even.
- If Odd = 0, then one cannot convert the integer to an odd integer by deleting any number of digits. Hence, print “Not Possible”.
- Otherwise, if Odd = 1, then to make the sum of digits even, one will have to delete that odd digit, which results in an even number. Therefore, print “Not Possible”.
- Now, count the number of digits to be deleted after the last occurrence of an odd digit and store it in a variable, say ans.
- If Odd is odd, then increment the count of ans by one, as one will have to delete an odd digit to make the sum even.
- Finally, print ans if none of the above cases satisfies.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum count of digits// required to be remove to make N odd and// the sum of digits of N evenvoid minOperations(string& N){ // Stores count of even digits int even = 0; // Stores count of odd digits int odd = 0; // Iterate over the digits of N for (auto it : N) { // If current digit is even if ((it - '0') % 2 == 0) { // Update even even++; } // Otherwise else { // Update odd odd++; } } // Base conditions if (odd == 0 || odd == 1) { cout << "Not Possible" << "\n"; } else { // Stores count of digits required to be // removed to make N odd and the sum of // digits of N even int ans = 0; // Iterate over the digits of N for (auto it : N) { // If current digit is even if ((it - '0') % 2 == 0) { // Update ans ans++; } // Otherwise, else { // Update ans ans = 0; } } // If count of odd digits is odd if (odd % 2) { // Update ans ans++; } // Finally print the ans cout << ans << endl; }}// Driver codeint main(){ // Input string string N = "12345"; // Function call minOperations(N);} |
Java
// Java implementation of the above approachimport java.util.*;class GFG{// Function to find minimum count of digits// required to be remove to make N odd and// the sum of digits of N evenstatic void minOperations(String N){ // Stores count of even digits int even = 0; // Stores count of odd digits int odd = 0; // Iterate over the digits of N for (int it : N.toCharArray()) { // If current digit is even if ((it - '0') % 2 == 0) { // Update even even++; } // Otherwise else { // Update odd odd++; } } // Base conditions if (odd == 0 || odd == 1) { System.out.print("Not Possible" + "\n"); } else { // Stores count of digits required to be // removed to make N odd and the sum of // digits of N even int ans = 0; // Iterate over the digits of N for (int it : N.toCharArray()) { // If current digit is even if ((it - '0') % 2 == 0) { // Update ans ans++; } // Otherwise, else { // Update ans ans = 0; } } // If count of odd digits is odd if (odd % 2 != 0) { // Update ans ans++; } // Finally print the ans System.out.print(ans +"\n"); }}// Driver codepublic static void main(String[] args){ // Input String String N = "12345"; // Function call minOperations(N);}}// This code is contributed by shikhasingrajput. |
Python3
# Python implementation of the above approach# Function to find minimum count of digits# required to be remove to make N odd and# the sum of digits of N evendef minOperations(N): # Stores count of even digits even = 0; # Stores count of odd digits odd = 0; # Iterate over the digits of N for it in N: # If current digit is even if (int(ord(it) - ord('0')) % 2 == 0): # Update even even += 1; # Otherwise else: # Update odd odd += 1; # Base conditions if (odd == 0 or odd == 1): print("Not Possible" + ""); else: # Stores count of digits required to be # removed to make N odd and the sum of # digits of N even ans = 0; # Iterate over the digits of N for it in N: # If current digit is even if (int(ord(it) - ord('0')) % 2 == 0): # Update ans ans += 1; # Otherwise, else: # Update ans ans = 0; # If count of odd digits is odd if (odd % 2 != 0): # Update ans ans += 1; # Finally print the ans print(ans, end=" ");# Driver codeif __name__ == '__main__': # Input String N = "12345"; # Function call minOperations(N);# This code is contributed by shikhasingrajput |
C#
// C# implementation of the above approachusing System;class GFG{// Function to find minimum count of digits// required to be remove to make N odd and// the sum of digits of N evenstatic void minOperations(String N){ // Stores count of even digits int even = 0; // Stores count of odd digits int odd = 0; // Iterate over the digits of N foreach (int it in N.ToCharArray()) { // If current digit is even if ((it - '0') % 2 == 0) { // Update even even++; } // Otherwise else { // Update odd odd++; } } // Base conditions if (odd == 0 || odd == 1) { Console.Write("Not Possible" + "\n"); } else { // Stores count of digits required to be // removed to make N odd and the sum of // digits of N even int ans = 0; // Iterate over the digits of N foreach (int it in N.ToCharArray()) { // If current digit is even if ((it - '0') % 2 == 0) { // Update ans ans++; } // Otherwise, else { // Update ans ans = 0; } } // If count of odd digits is odd if (odd % 2 != 0) { // Update ans ans++; } // Finally print the ans Console.Write(ans +"\n"); }}// Driver codepublic static void Main(String[] args){ // Input String String N = "12345"; // Function call minOperations(N);}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript implementation of the above approach// Function to find minimum count of digits// required to be remove to make N odd and// the sum of digits of N evenfunction minOperations(N){ // Stores count of even digits var even = 0; // Stores count of odd digits var odd = 0; // Iterate over the digits of N for (var it =0; it<N.length; it++) { // If current digit is even if ((N[it] - '0') % 2 == 0) { // Update even even++; } // Otherwise else { // Update odd odd++; } } // Base conditions if (odd == 0 || odd == 1) { document.write( "Not Possible" + "<br>"); } else { // Stores count of digits required to be // removed to make N odd and the sum of // digits of N even var ans = 0; // Iterate over the digits of N for (var it =0; it<N.length; it++){ // If current digit is even if ((N[it] - '0') % 2 == 0) { // Update ans ans++; } // Otherwise, else { // Update ans ans = 0; } } // If count of odd digits is odd if (odd % 2) { // Update ans ans++; } // Finally print the ans document.write( ans ); }}// Driver code// Input stringvar N = "12345";// Function callminOperations(N);</script> |
Output:
1
Time Complexity: O(log10(N))
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!
