Given a positive integer N, the task is to find the largest possible value of N after any number of swaps is made between digits that are present in positions with the same parity.
Examples:
Input: N = 12345
Output: 54321
Explanation: Swap 1 with 5 [both in odd positions],
and 2 with 4 [both in even positions] to obtain 54321.Input: N = 738946
Output: 897643
Approach:
The problem can be solved by storing odd indexed and even indexed digits in two maxHeaps, and creating new number that has both parity indexed digits sorted in descending order.
The following steps can be used to solve this problem:
- Initialize 2 maxHeaps even and odd.
- Iterate over digits of the number and store even indexed digits in even maxHeap and odd indexed digits in odd maxHeap.
- Create a new number by popping values from maxHeaps, now new number would have both even indexed digits and odd indexed digits in decreasing order.
- Return this number as it is the maximum.
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to return largest// combination of integerint largestInteger(int num){ // Declare two MaxHeap for // even and odd index priority_queue<int> Even; priority_queue<int> Odd; int C = 0, t = num; // Calculate No of Digits in N while (t) { C++; t /= 10; } // If last digit index is even then set // flag = 1 else flag = 0 bool flag = C & 1 ? 1 : 0; // Push even indexed element in Even MaxHeap // and odd indexed element in Odd MaxHeap while (num) { if (flag) Even.push(num % 10); else Odd.push(num % 10); flag = !flag; num /= 10; } // Initialize answer int ans = 0; // While both the Heap is non empty while (!Even.empty() && !Odd.empty()) { ans = (ans * 10 + Even.top()); Even.pop(); ans = (ans * 10 + Odd.top()); Odd.pop(); } // If there is extra even index element if // Count of digit is odd if (C & 1) ans = ans * 10 + Even.top(); // Return answer return ans;}// Driver Codeint main(){ int N = 738946; // Function call cout << largestInteger(N) << endl; return 0;} |
Java
import java.io.*;import java.util.*;class GFG { // Java code to implement the above approach // Function to return largest// combination of integerpublic static int largestInteger(int num){ // Declare two MaxHeap for // even and odd index PriorityQueue<Integer>Even= new PriorityQueue<>((a,b)->b-a); PriorityQueue<Integer>Odd= new PriorityQueue<>((a,b)->b-a); int C = 0, t = num; // Calculate No of Digits in N while (t > 0) { C++; t /= 10; } // If last digit index is even then set // flag = 1 else flag = 0 boolean flag = (C & 1)>0 ? true : false; // Push even indexed element in Even MaxHeap // and odd indexed element in Odd MaxHeap while (num > 0) { if (flag) Even.add(num % 10); else Odd.add(num % 10); flag = !flag; num /= 10; } // Initialize answer int ans = 0; // While both the Heap is non empty while (!Even.isEmpty() && !Odd.isEmpty()) { ans = (ans * 10 + Even.peek()); Even.remove(); ans = (ans * 10 + Odd.peek()); Odd.remove(); } // If there is extra even index element if // Count of digit is odd if ((C & 1) > 0) ans = ans * 10 + Even.peek(); // Return answer return ans;}// Driver Codepublic static void main (String[] args){ int N = 738946; // Function call System.out.println(largestInteger(N)); }}// This code is contributed by satwik4409. |
Python3
from queue import PriorityQueue# python3 code to implement the above approach# Function to return largest# combination of integerdef largestInteger(num): # Declare two MaxHeap for # even and odd index Even = PriorityQueue() Odd = PriorityQueue() C = 0 t = num # Calculate No of Digits in N while (t): C += 1 t //= 10 # If last digit index is even then set # flag = 1 else flag = 0 flag = 1 if C & 1 else 0 # Push even indexed element in Even MaxHeap # and odd indexed element in Odd MaxHeap while (num): if (flag): Even.put(-(num % 10)) else: Odd.put(-(num % 10)) flag = not flag num //= 10 # Initialize answer ans = 0 # While both the Heap is non empty while ((not Even.empty()) and (not Odd.empty())): ans = (ans * 10 + -Even.get()) ans = (ans * 10 + -Odd.get()) # If there is extra even index element if # Count of digit is odd if (C & 1): ans = ans * 10 + -Even.get() # Return answer return ans# Driver Codeif __name__ == "__main__": N = 738946 # Function call print(largestInteger(N)) # This code is contributed by rakeshsahni |
C#
using System;using System.Collections.Generic;class HelloWorld { // Function to return largest // combination of integer static int largestInteger(int num) { // Declare two MaxHeap for // even and odd index List<int> Even = new List<int>(); List<int> Odd = new List<int>(); int C = 0, t = num; // Calculate No of Digits in N while (t != 0) { C++; t /= 10; } // If last digit index is even then set // flag = 1 else flag = 0 bool flag = false; if ((C & 1) != 0) flag = true; // Push even indexed element in Even MaxHeap // and odd indexed element in Odd MaxHeap while (num != 0) { if (flag) Even.Add(num % 10); else Odd.Add(num % 10); flag = !flag; num /= 10; } var E = Even.ToArray(); var O = Odd.ToArray(); Array.Sort(E); Array.Sort(O); // Initialize answer int ans = 0; // While both the Heap is non empty int i = E.Length - 1; int j = O.Length - 1; while (i >= 0 && j >= 0) { ans = (ans * 10 + E[i]); i--; ans = (ans * 10 + O[j]); j--; } // If there is extra even index element if // Count of digit is odd if ((C & 1) != 0) ans = ans * 10 + E[i]; // Return answer return ans; } static void Main() { int N = 738946; // Function call Console.Write(largestInteger(N)); }}// This code is contributed by garg28harsh. |
Javascript
// <script>// Javascript code to implement the above approachfunction PriorityQueue () { var collection = []; this.printCollection = function() { (console.log(collection)); }; this.enqueue = function(element){ if (this.isEmpty()){ collection.push(element); } else { var added = false; for (var i=0; i<collection.length; i++){ if (element[1] < collection[i][1]){ //checking priorities collection.splice(i,0,element); added = true; break; } } if (!added){ collection.push(element); } } }; this.dequeue = function() { var value = collection.shift(); return value[0]; }; this.front = function() { return collection[0]; }; this.size = function() { return collection.length; }; this.isEmpty = function() { return (collection.length === 0); };}// Function to return largest// combination of integerfunction largestInteger( num){ // Declare two MaxHeap for // even and odd index let Even = new PriorityQueue(); let Odd = new PriorityQueue(); /*priority_queue<int> Even; priority_queue<int> Odd;*/ let C = 0; let t = num; // Calculate No of Digits in N while (t) { C++; t /= 10; } // If last digit index is even then set // flag = 1 else flag = 0 let flag = C & 1 ? true : false; // Push even indexed element in Even MaxHeap // and odd indexed element in Odd MaxHeap while (num) { if (flag) Even.enqueue(num % 10); else Odd.enqueue(num % 10); flag = !flag; num /= 10; } // Initialize answer let ans = 0; // While both the Heap is non empty while (Even.size()>0 && Odd.size()>0 ) { ans = (ans * 10 + Even.front()); Even.dequeue(); ans = (ans * 10 + Odd.front()); Odd.dequeue(); } // If there is extra even index element if // Count of digit is odd if (C & 1) ans = ans * 10 + Even.front(); // Return answer return ans;}// Driver Code let N = 738946; // Function call console.log(largestInteger(N)); // This code is contributed by akashish__ </script> |
Output
897643
Time Complexity: O(log N)
Auxiliary Space: O(log N)
