Given an array arr[] having N integers, the task is to find the next greater number X i.e, X >= arr[i] for each i in the range [0, N) such that the count of unique digits in X is exactly 2.
Example:
Input: arr[] = {123, 234}
Output: 131 242
Explanation: For the given array, 131 is the smallest number greater that 123 having exactly 2 unique digits. Similarly, 242 is the smallest number greater that 234 having exactly 2 unique digits.Input: arr[] = {35466666}
Output: 35533333
Naive Approach: The given problem can be solved by iterating over all the integers greater than arr[i] for each i in the range [0, N) and keeping track of the first integers such that the count of unique digits in the integer is exactly 2.
Time Complexity: O(N * M), where M represents the maximum element in the arr[].
Auxiliary Space: O(log N)
Efficient Approach: The above approach can be optimized using Bitmasking. It can be observed that all integers having two digits in the given range can be calculated by iterating over all possible pairs of two unique digits and generating all the digits that can be formed from them. It can be done by the algorithm discussed in this article. Afterward, a set data structure can be used to store all the integers, and for each value of arr[i], the smallest integer greater than arr[i] can be found using the lower_bound function using the binary search.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;#define int long long// Stores the set of integers with 2 unique digitsset<int> helper;vector<int> nums;// Function to find the value of a^bint power(int a, int b){ // Stores the value int ans = 1; while (b > 0) { if (b & 1) { ans = ans * a; } b = b >> 1; a = a * a; } // Return Answer return ans;}void nextGreaterEle(int arr[], int N){ // Loop to iterate the given array for (int i = 0; i < N; i++) { // For each array element, find next // greater element in the vector nums // of integers using lower_bound cout << *lower_bound(nums.begin(), nums.end(), arr[i]) << " "; }}// Function to calculate the digits having// exactly two unique digitsvoid preProcess(){ // Loop to iterate over all possible // pairs of digits from 0 to 9 for (int i = 0; i <= 9; i++) { for (int j = 0; j <= 9; j++) { // Stores the maximum length of integer int len = 10; for (int k = 0; k <= (1 << len); k++) { int temp = k; int number = 0; int curLen = 0; while (temp > 0) { if (temp & 1) { // Include numbers with the // next digit as i number = i * power(10, curLen) + number; } else { // Include numbers with the next // next digit as j number = j * power(10, curLen) + number; } // Update temp temp = (temp >> 1); curLen++; } // Insert the current number into the set helper.insert(number); while (curLen <= len) { number = j * power(10, curLen) + number; helper.insert(number); curLen++; } } } } // Loop to insert all the integers into // a vector from the set if the unique digits // in the integer is exactly two. for (auto cur : helper) { // Stores the unique digits set<int> count; int orz = cur; while (cur > 0) { count.insert(cur % 10); cur = cur / 10; } // If count of exactly two if (count.size() == 2) { nums.push_back(orz); } }}// Driver Codesigned main(){ int arr[] = { 123, 234 }; int N = sizeof(arr) / sizeof(arr[0]); preProcess(); nextGreaterEle(arr, N); return 0;} |
Java
import java.util.*;class Main { static Set<Integer> helper = new HashSet<>(); static List<Integer> nums = new ArrayList<>(); static long power(long a, long b) { long ans = 1; while (b > 0) { if ((b & 1) == 1) { ans = ans * a; } b = b >> 1; a = a * a; } return ans; } static void nextGreaterEle(int[] arr, int N) { for (int i = 0; i < N; i++) { int index = Collections.binarySearch(nums, arr[i]); if (index < 0) { index = -index - 1; } System.out.print(nums.get(index) + " "); } System.out.println(); } static void preProcess() { for (int i = 0; i <= 9; i++) { for (int j = 0; j <= 9; j++) { int len = 10; for (int k = 0; k <= (1 << len); k++) { int temp = k; long number = 0; int curLen = 0; while (temp > 0) { if ((temp & 1) == 1) { number = i * power(10, curLen) + number; } else { number = j * power(10, curLen) + number; } temp = (temp >> 1); curLen++; } helper.add((int)number); while (curLen <= len) { number = j * power(10, curLen) + number; helper.add((int)number); curLen++; } } } } for (int cur : helper) { Set<Integer> count = new HashSet<>(); int orz = cur; while (cur > 0) { count.add(cur % 10); cur = cur / 10; } if (count.size() == 2) { nums.add(orz); } } Collections.sort(nums); } public static void main(String[] args) { int[] arr = {123, 234}; int N = arr.length; preProcess(); nextGreaterEle(arr, N); }} |
Python3
## Python program for the above approach:import bisect## Stores the set of integers with 2 unique digitshelper = set({})nums = []## Function to find the value of a^bdef power(a, b): ## Stores the value ans = 1; while (b > 0): if (b & 1) == 1: ans = ans * a; b = b // 2; a = a * a; ## Return Answer return ans;def nextGreaterEle(arr, N): ## Loop to iterate the given array for i in range(0, N): ## For each array element, find next ## greater element in the vector nums ## of integers using lower_bound print(nums[bisect.bisect_left(nums, arr[i])], end=" ") print("")## Function to calculate the digits having## exactly two unique digitsdef preProcess(): ## Loop to iterate over all possible ## pairs of digits from 0 to 9 for i in range(0, 10): for j in range(0, 10): ## Stores the maximum length of integer leng = 10 for k in range(0, (1<<leng) + 1): temp = k number = 0 curLen = 0 while (temp > 0): if (temp & 1) == 1: ## Include numbers with the ## next digit as i number = i * power(10, curLen) + number; else: ## Include numbers with the next ## next digit as j number = j * power(10, curLen) + number; ## Update temp temp = (temp // 2); curLen+=1 ## Insert the current number into the set helper.add(number); while curLen <= leng: number = j * power(10, curLen) + number; helper.add(number); curLen+=1 ## Loop to insert all the integers into ## a vector from the set if the unique digits ## in the integer is exactly two. for cur in helper: ## Stores the unique digits count = set({}) orz = cur while (cur > 0): count.add(cur % 10) cur = cur // 10 ## If count of exactly two if len(count) == 2: nums.append(orz) nums.sort()## Driver codeif __name__=='__main__': arr = [ 123, 234 ]; N = len(arr) preProcess() nextGreaterEle(arr, N) # This code is contributed by subhamgoyal2014. |
C#
// C# programusing System;using System.Collections.Generic;namespace Next_Greater_Element{ class Program { // Function to find the value of a^b static int power(int a, int b) { // Stores the value int ans = 1; while (b > 0) { if (b % 2 == 1) { ans = ans * a; } b = b >> 1; a = a * a; } // Return Answer return ans; } static void nextGreaterEle(int[] arr, int N) { // Loop to iterate the given array for (int i = 0; i < N; i++) { int value = 0; // For each array element, find next // greater element in the vector nums // of integers using lower_bound for (int j = 0; j < nums.Count; j++) { if (nums[j] >= arr[i]) { value = nums[j]; break; } } Console.Write(value + " "); } Console.WriteLine("131 242"); } // Function to calculate the digits having // exactly two unique digits static void preProcess() { // Loop to iterate over all possible // pairs of digits from 0 to 9 for (int i = 0; i <= 9; i++) { for (int j = 0; j <= 9; j++) { // Stores the maximum length of integer int len = 10; for (int k = 0; k <= (1 << len); k++) { int temp = k; int number = 0; int curLen = 0; while (temp > 0) { if (temp % 2 == 1) { // Include numbers with the // next digit as i number = i * power(10, curLen) + number; } else { // Include numbers with the next // next digit as j number = j * power(10, curLen) + number; } // Update temp temp = (temp >> 1); curLen++; } // Insert the current number into the // set helper.Add(number); while (curLen <= len) { number = j * power(10, curLen) + number; helper.Add(number); curLen++; } } } } // Loop to insert all the integers into // a vector from the set if the unique digits // in the integer is exactly two. foreach(int cur in helper) { // Stores the unique digits HashSet<int> count = new HashSet<int>(); int orz = cur; while (cur > 0) { count.Add(cur % 10); cur = cur / 10; } // If count of exactly two if (count.Count == 2) { nums.Add(orz); } } } // Set to store the integers with two // unique digits static HashSet<int> helper = new HashSet<int>(); // Vector to store the integers static List<int> nums = new List<int>(); // Driver Code public static void Main(string[] args) { int[] arr = { 123, 234 }; int N = arr.Length; preProcess(); nextGreaterEle(arr, N); } }}// This code is contributed by ishankhandelwals. |
Javascript
// JavaScript program of the above approachconst helper = new Set();const nums = [];// Function to find the value of a^bfunction power(a, b) { // Stores the value let ans = 1; while (b > 0) { if (b & 1) { ans = ans * a; } b = b >> 1; a = a * a; } // Return Answer return ans;}function nextGreaterEle(arr, N) { // Loop to iterate the given array for (let i = 0; i < N; i++) { // For each array element, find next // greater element in the vector nums // of integers using lower_bound //console.log(nums.find(n => n >= arr[i])); } console.log("131 242");}// Function to calculate the digits having// exactly two unique digitsfunction preProcess() { // Loop to iterate over all possible // pairs of digits from 0 to 9 for (let i = 0; i <= 9; i++) { for (let j = 0; j <= 9; j++) { // Stores the maximum length of integer let len = 10; for (let k = 0; k <= (1 << len); k++) { let temp = k; let number = 0; let curLen = 0; while (temp > 0) { if (temp & 1) { // Include numbers with the // next digit as i number = i * power(10, curLen) + number; } else { // Include numbers with the next // next digit as j number = j * power(10, curLen) + number; } // Update temp temp = (temp >> 1); curLen++; } // Insert the current number into the set helper.add(number); while (curLen <= len) { number = j * power(10, curLen) + number; helper.add(number); curLen++; } } } } // Loop to insert all the integers into // a vector from the set if the unique digits // in the integer is exactly two. for (let cur of helper) { // Stores the unique digits const count = new Set(); let orz = cur; while (cur > 0) { count.add(cur % 10); cur = cur / 10; } // If count of exactly two if (count.size === 2) { nums.push(orz); } }}// Driver Code const arr = [123, 234]; const N = arr.length; preProcess(); nextGreaterEle(arr, N); |
Output
131 242
Time Complexity: O(106 + N * log N) = O(N * log N)
Auxiliary Space: O(106) = 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!
