Given a non-negative number N, the task is to convert the number by deleting some digits of the number, such that the sum of the digits becomes even but the number is odd. In case there is no possible number, then print -1.
Note: There can be multiple numbers possible for a given N.
Examples:
Input: N = 18720
Output: 17
Explanation:
After Deleting 8, 2, 0 digits the number becomes 17 which is odd and the digit-sum is 8 which is even.
Input: N = 3
Output: -1
Explanation:
There is no possibility such that number becomes odd and the digit-sum is even.
Approach:
The idea is to use the fact that “Even number of odd digits will give the sum to even number”. So, If the digits in the number contain even count of odd digits then it is possible to convert the number otherwise converting such number is not possible.
Below is the implementation of the above approach.
C++
// C++ implementation to convert// a number into odd number such// that digit-sum is odd#include <bits/stdc++.h>using namespace std;// Function to convert a number into// odd number such that digit-sum is oddvoid convertthenumber(int n){ string s = to_string(n); string res; // Loop to find any first two // odd number such that their // sum is even and number is odd for (int i = 0; i < s.length(); i++) { if (s[i] == '1' || s[i] == '3' || s[i] == '5' || s[i] == '7' || s[i] == '9') res += s[i]; if (res.size() == 2) break; } // Print the result if (res.size() == 2) cout << res << endl; else cout << "-1" << endl;}// Driver Codeint main(){ int n = 18720; convertthenumber(n); return 0;} |
Java
// Java implementation to convert // a number into odd number such // that digit-sum is odd import java.util.*;import java.lang.*;import java.io.*;class Main { // Function to convert a number into // odd number such that digit-sum is odd static void convertthenumber(int n) { String s = Integer.toString(n); String res = ""; // Loop to find any first two // odd number such that their // sum is even and number is odd for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '1' || s.charAt(i) == '3' || s.charAt(i) == '5' || s.charAt(i) == '7' || s.charAt(i) == '9') res += s.charAt(i); if (res.length() == 2) break; } // Print the result if (res.length() == 2) System.out.println(res); else System.out.println(-1); } // Driver code public static void main (String[] args) { int n = 18720; convertthenumber(n); } } // This code is contributed by Subhadeep Gupta |
Python3
# Python3 implementation to convert # a number into odd number such # that digit-sum is odd # Function to convert a number into # odd number such that digit-sum is odd def convertthenumber(n) : s = str(n); res = ""; # Loop to find any first two # odd number such that their # sum is even and number is odd for i in range(len(s)) : if (s[i] == '1' or s[i] == '3' or s[i] == '5' or s[i] == '7' or s[i] == '9') : res += s[i]; if (len(res) == 2) : break; # Print the result if (len(res) == 2) : print(res); else : print("-1"); # Driver Code if __name__ == "__main__" : n = 18720; convertthenumber(n); # This code is contributed by AnkitRai01 |
C#
// C# implementation to convert// a number into odd number such// that digit-sum is oddusing System; class GFG { // Function to convert a number into// odd number such that digit-sum is oddstatic void convertthenumber(int n){ String s = n.ToString(); String res = ""; // Loop to find any first two // odd number such that their // sum is even and number is odd for (int i = 0; i < s.Length; i++) { if (s[i] == '1' || s[i] == '3' || s[i] == '5' || s[i] == '7' || s[i] == '9') res += s[i]; if (res.Length == 2) break; } // Print the result if (res.Length == 2) Console.WriteLine(res); else Console.WriteLine(-1);}// Driver code public static void Main (String[] args) { int n = 18720; convertthenumber(n);} } // This code is contributed by Mohit kuamr 29 |
Javascript
<script>// Javascript implementation to convert// a number into odd number such// that digit-sum is odd// Function to convert a number into// odd number such that digit-sum is oddfunction convertthenumber(n){ var s = n.toString(); var res = ""; var i; // Loop to find any first two // odd number such that their // sum is even and number is odd for (i = 0; i < s.length; i++) { if (s[i] == '1' || s[i] == '3' || s[i] == '5' || s[i] == '7' || s[i] == '9') res += s[i]; if (res.length == 2) break; } // Print the result if (res.length == 2) document.write(res); else document.write("-1");}// Driver Code var n = 18720; convertthenumber(n);</script> |
Output:
17
Time Complexity: O(|s|), where |s| represents the number of digits in the given number.
Auxiliary Space: O(|s|)
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!
