Given an integer N, the task is to find the minimum number of operations required to make N even such that in one operation prefix of any length can be reversed. If it’s not possible to make N as even number print -1.
Examples:
Input: N = 376502
Output: 0
Explanation:
– N is already divisible by 2, hence it is an even number so the total number of prefix swaps will be 0.Input: N = 36543
Output: 2
Explanation:
– N is not an even number so to make it even first swap the prefix of length 2. Now N=63543
– Now swap the prefix of length 5 and N=34536.
Approach:
There can be 2 cases.
- N is an even number
- N is an odd number.
Now,
- If N is an even number, the number of minimum steps to make N an even number will be 0.
- If N is an odd number, there can be 3 cases.
- N does not contain any even digits. In this case, it is impossible to make N an even number so the answer will be -1.
- N contains even digits and the first digit of N is even. In this case, we can swap the whole number, so the minimum number of steps to make N an even number will be 1.
- N contains even digits and the first digit of N is not even. In this case, we can first swap the prefix till any even digit and then swap the whole number, so the minimum number of steps to make N an even number will be 2.
Follow the steps below to solve the problem:
- Initialize the string s[] as the string representation of N.
- Initialize the variable ans as -1 and len as the length of the string s[].
- If (s[len-1] – ‘0’)%2==0 the set ans as 0.
- Else, perform the following tasks:
- If the first character of the string s[] is even then set ans as 1.
- Iterate over the range [0, len) using the variable i and perform the following tasks:
- If s[i] is even, then set ans as 2 and break.
- After performing the above steps, print the value of ans as the answer.
Below is the implementation for the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum number// of steps required to make N an even numbervoid MinSteps(int N){ // Converting N into string string s = to_string(N); int ans = -1; // Number of digits in N int len = s.size(); // If the number is even if ((s[len - 1] - '0') % 2 == 0) { ans = 0; } else { // If the first digit is even if ((s[0] - '0') % 2 == 0) { ans = 1; } else { // Checking if s contains // any even digits for (int i = 0; i < len; i++) { if ((s[i] - '0') % 2 == 0) { ans = 2; break; } } } } // Printing the minimum number // of steps to make N an even number cout << ans << "\n";}// Driver Codeint main(){ int N; N = 36543; MinSteps(N);} |
Java
// Java code for the above approachimport java.util.*;class GFG{ // Function to find minimum number // of steps required to make N an even number static void MinSteps(int N) { // Converting N into String String s = String.valueOf(N); int ans = -1; // Number of digits in N int len = s.length(); // If the number is even if ((s.charAt(len - 1) - '0') % 2 == 0) { ans = 0; } else { // If the first digit is even if ((s.charAt(0) - '0') % 2 == 0) { ans = 1; } else { // Checking if s contains // any even digits for (int i = 0; i < len; i++) { if ((s.charAt(i) - '0') % 2 == 0) { ans = 2; break; } } } } // Printing the minimum number // of steps to make N an even number System.out.print(ans+ "\n"); } // Driver Code public static void main(String[] args) { int N; N = 36543; MinSteps(N); }}// This code is contributed by 29AjayKumar |
Python3
# python3 code for the above approach# Function to find minimum number# of steps required to make N an even numberdef MinSteps(N): # Converting N into string s = str(N) ans = -1 # Number of digits in N le = len(s) # If the number is even if ((ord(s[le - 1]) - ord('0')) % 2 == 0): ans = 0 else: # If the first digit is even if ((ord(s[0]) - ord('0')) % 2 == 0): ans = 1 else: # Checking if s contains # any even digits for i in range(0, le): if ((ord(s[i]) - ord('0')) % 2 == 0): ans = 2 break # Printing the minimum number # of steps to make N an even number print(ans)# Driver Codeif __name__ == "__main__": N = 36543 MinSteps(N)# This code is contributed by rakeshsahni |
C#
// C# code for the above approachusing System;class GFG{ // Function to find minimum number // of steps required to make N an even number static void MinSteps(int N) { // Converting N into String String s = Convert.ToString(N); int ans = -1; // Number of digits in N int len = s.Length; // If the number is even if ((s[len - 1] - '0') % 2 == 0) { ans = 0; } else { // If the first digit is even if ((s[0] - '0') % 2 == 0) { ans = 1; } else { // Checking if s contains // any even digits for (int i = 0; i < len; i++) { if ((s[i] - '0') % 2 == 0) { ans = 2; break; } } } } // Printing the minimum number // of steps to make N an even number Console.Write(ans + "\n"); } // Driver Code public static void Main() { int N; N = 36543; MinSteps(N); }}// This code is contributed by Saurabh Jaiswal |
Javascript
<script>// JavaScript code for the above approach// Function to find minimum number// of steps required to make N an even numberconst MinSteps = (N) => { // Converting N into string let s = N.toString(); let ans = -1; // Number of digits in N let len = s.length; // If the number is even if ((s.charCodeAt(len - 1) - '0'.charCodeAt(0)) % 2 == 0) { ans = 0; } else { // If the first digit is even if ((s.charCodeAt(0) - '0'.charCodeAt(0)) % 2 == 0) { ans = 1; } else { // Checking if s contains // any even digits for(let i = 0; i < len; i++) { if ((s.charCodeAt(i) - '0'.charCodeAt(0)) % 2 == 0) { ans = 2; break; } } } } // Printing the minimum number // of steps to make N an even number document.write(`${ans}<br/>`);}// Driver Codelet N = 36543;MinSteps(N);// This code is contributed by rakeshsahni</script> |
Output
2
Time Complexity: O(len), where len is the length of the string.
Auxiliary Space: O(len)
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!