Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
Approach 1: Brute Force
3.1.1.
C++ implementation
3.1.2.
Complexities
3.2.
Approach 2: Using bitmasking
3.2.1.
C++ implementation
3.2.2.
Complexities
4.
Frequently asked questions
5.
Key Takeaways
Last Updated: Mar 27, 2024

Find the next greater number formed with exactly two unique digits for each array element

Author Shreya Deep
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This article describes how to find, for each array element, the next greater number formed with exactly two unique digits.

Problem Statement

Given an array a, of n numbers, for each number a[i], find the next greater number from a[i], which has only two unique digits in it. 

For example:

Input

n = 2, array = [238, 183]

Output

[242, 188]

Explanation:

The next greater number having exactly two unique digits for 238 is 242 and for 183 is 188.

Also see, Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution Approach

Approach 1: Brute Force

The most straightforward approach to solve this problem is to iterate through the whole array, and for each iteration, keep going to the numbers greater than a[i]. Once you find a number greater than a[i], which has only two unique digits in it, that number is the answer for a[i]. For finding, if a number contains only two unique digits in it or not, insert all the digits of the number in a set and check if the size of the set is two or not in the end. If yes, then the number contains only two unique digits. Else not.

Why are we using the set here? Because a set doesn't contain any duplicate numbers. So, if a digit is repeated, it is only stored once in the set. Thus, the size of the set should be 2 in the end.

Steps of implementation are:

  • Input the given array
  • Find the size of the given array.
  • Iterate through the array
  • Make a copy of a[i] in x. For each a[i], keep increasing x until the number x has two unique digits. Since x has started from a[i], we are sure that it is always greater or equal to a[i]. For checking, if x contains exactly two unique digits or not, call the function contains_two_unique_digits. In this function:
    • Make a set unique_digits, which contains the digits of the number.
    • Insert the digits of the number into the set.
    • Check if the size of the size is two or not. If yes, return true. Else, return false.
  • Print x.

C++ implementation

#include<bits/stdc++.h>
using namespace std;

bool contains_two_unique_digits(int num){
    /*
        Make a set unique_digits, which contains the digits of the number.
    */
    set<int>unique_digits;
    /*
        Insert the digits of the number into the set.
    */
    while(num){
        unique_digits.insert(num%10);
        num/=10;
    }
    /*
        Check if the size is 2 or not. If yes, return true. Else, return false.
    */
    if(unique_digits.size()==2){
        return true;
    }
    else{
        return false;
    }
}

int main(){
    /*
        Input the given array
    */
    int a[] = { 238, 183 };
    /*
        Find the size of the given array
    */
    int n = sizeof(a) / sizeof(a[0]);
    /*
        Iterate through the array
    */
    for(int i=0;i<n;i++){
        /*
            Make a copy of a[i] in x.
            For each a[i], keep increasing x until the number x has two unique digits. Since x has started from a[i], we are sure that it is always greater or equal to a[i].
        */
        int x = a[i];
        while(!contains_two_unique_digits(x)){
            x++;
        }
        /*
            Print x.
        */
        cout<<x<<" ";
    }
    cout<<endl;
    return 0;
}

Output

242 188

Complexities

Time complexity

O(n*x), where n is the number of elements in the array and x is the maximum difference between the answer of the ith term and a[i].

Reason: We're iterating on each a[i] once. This takes O(n) time. Now, for each a[i], we're also running the while loop until we get a number that contains two unique digits. In the worst case, this while loop runs for "the maximum difference of the answer of the ith index and a[i]" times. The total time complexity is O(n*x), where x is the maximum difference between the ith index's answer and a[i]. Note that finding if a number contains two unique digits takes only log(length of the number) = log(10) in the worst case. This is a constant value, so we can consider it a constant time.

Space complexity

O(1)

Reason: The only space taken here is by the integer variables, which is constant, and by the set unique_digits, which is also constant as there can be a maximum of 10 different digits stored in the set anytime. Therefore, we can say that all the spaces are constant.

Approach 2: Using bitmasking

This problem can also be solved by doing some precomputation. First, we calculate all the numbers till 10^10, which has only two unique digits. Let's store these numbers in a sorted vector. Now, for each a[i], we have just found the next greater element in the vector. Think of an inbuilt function that does this. Which is it? You guessed correctly. The stl lower_bound() function finds the next greater number of a number. So, we can call this function on the vector for the current a[i], and the answer returned by it is the answer for that a[i]. 

But the real question is, how to find all the numbers till 10^10, which have two unique digits in them? Let's see how to find that. 

Think of how many combinations of two unique digits are there. 90, right? Because the digits are only 10 (from 0 to 9). And for each of these 10 digits, there are nine options to choose from. So, if we want two different digits, there are total 9x10=90 ways to choose from. 

For example, (01, 02, 03, ...09, 10, 12, 13, …, 19, 21, 23, … and so on.) So, to make numbers from these combinations, we can make numbers of different lengths. But till how much length do we want? Not more than 10, right? Because the limit of a[i] is 10^9.

 So, we loop through all the combinations and all the lengths and find the numbers. One thing to notice here is that, for each length x, we have x places to be filled. Now, for each place, you have two choices. To fill that place with digit a or with the digit b. 

We can see this as a bitmasking problem also, and for each place, if in the binary representation of x, the number at that place is '1', then assign a at the place; otherwise, b.

Steps of implementation are:

  • Input the given array
     
  • Find the size of the given array.
     
  • Call the function that precalculates numbers less equal to 10^10 having two unique digits.
     
  • In the function preCalculation():
    • Loop through the different combinations of two unique digits from 0 to 9.
       
    • If the combination doesn't contain two unique digits, i.e., if i==j, continue and move to the next j.
       
    • Else, find the different numbers formed using these two unique digits. Fix the maximum length of the numbers to 10.
       
    • Loop through different lengths by doing bitmasking on the numbers from 0 to 2^10.
       
    • Declare three variables, x, number, and current_length. X denotes the current bitmask we're at. Number denotes the current number formed, and current_length denotes the length of the current number formed.
       
    • If the last digit in the binary representation of the bitmask is 1, add the digit i to the number. For adding, we have to add at the front. And since it's an integer, we have to add the digit by multiplying the place and the face value and then adding it to the current value of the number.
       
    • Similarly, if the last bit is not 1, we must add j to the current number in front.
       
    • After every addition, decrease the required length by 1, i.e., divide bitmask by 2.
       
    • Also, increase the current length of the number because one more digit is now added.
       
    • Once the number is calculated, push it into the numbers set.
       
    • For each number in the numbers set, check if the number of unique digits in it is two or not. If yes, push that number into the nums vector, which contains all the two unique digit numbers.
       
    • To find out the number of unique digits, make a set (unique_count) containing the current number's digits.
       
    • Insert all the digits of the number in the set unique_count.
       
    • If the unique_count set has size 2, there are two unique digits in the number. So, push the number into the vector nums.
       
  • Print the lower bound of each a[i] from the vector nums.

Note: In the implementation, we are using the fast exponentiation method for calculating the power of 2.

C++ implementation

#include <bits/stdc++.h>
using namespace std;

#define int long long

set<int> numbers;
vector<int> nums;

int exponentiation(int number, int power){
    int ans = 1;
    while (power > 0) {
        if (power & 1) {
            ans = ans * number;
        }
        power = power >> 1;
        number = number * number;
    }
    return ans;
}

void preCalculation(){
    /*
        Loop through the different combinations of two unique digits from 0 to 9.
    */
    for (int i = 0; i <= 9; i++) { 
        for (int j = 0; j <= 9; j++) {
            /*
                If the combination doesn't contain two unique digits, i.e., if i==j, continue and move to the next j.
            */
            if(i==j){
                continue;
            }
            /*
                Else, find the different numbers that can be formed using these two unique digits. Fix the maximum length of the numbers to 10.
            */
            int max_length = 10;
            /*
                Loop through different lengths by doing bitmasking on all the numbers from 0 to 2^10.
            */
            for (int k = 0; k <= (1 << max_length); k++) {
                int x = k;
                int number = 0;
                int current_length = 0;
                /*
                    Declare three variables, x, number and current_length. x denotes the current bitmask we're at. number denotes the number current number formed, and current_length denotes the length of the current number formed.
                */
                while (x > 0) {
                    /*
                        If the last digit in the binary representation of the bitmask is 1, add the digit i to the number. For adding, we have to add at the front. And since it's an integer, we have added the digit by multiplying the place and the face value and then, adding it to the current value of the number.
                    */
                    if (x & 1) {
                        number = i * exponentiation(10, current_length)+ number;
                    }
                    /*
                        Similarly, if the last bit is not 1, we have to add j to the current number in front.
                    */
                    else {
                        number = j * exponentiation(10, current_length)+ number;
                    }
                    /*
                        After every addition, decrease the required length by 1, i.e., divide bitmask by 2.
                    */
                    x = (x >> 1);
                    /*
                        Also, increase the current length of the number because one more digit is now added.
                    */
                    current_length++;
                }
                /*
                    Once the number is calculated, push it into the numbers set.
                */
                numbers.insert(number);
            }
        }
    }
    /*
        For each number in the numbers set, check if the number of unique digits in it is 2 or not. If yes, then, push that number into the nums vector which contains all the 2 unique digit numbers.
    */
    for (auto current_number : numbers) {
        /*
            For finding out the number of unique digits, make a set (unique_count) which will contain the digits of the current number.
        */
        set<int> unique_count;
        int temp = current_number;
        /*
            Insert all the digits of the number in the set unique_count.
        */
        while (current_number > 0) {
            unique_count.insert(current_number % 10);
            current_number = current_number / 10;
        }
        /*
            If the unique_count set has size 2, this means there are 2 unique digits in the number. So, push the number into the vector nums.
        */
        if (unique_count.size() == 2) {
            nums.push_back(temp);
        }
    }
}

int32_t main(){
    /*
        Input the given array
    */
    int a[] = { 234, 183 };
    /*
        Find the size of the given array
    */
    int n = sizeof(a) / sizeof(a[0]);
    /*
        Call the function which precalculates the numbers less equal to 10^10 having two unique digits
    */
    preCalculation();
    /*
        Print the lower bound of each a[i] from the vector nums.
    */
    for (int i = 0; i < n; i++) {
        cout << *lower_bound(nums.begin(), nums.end(),a[i])<< " ";
    }
    cout<<endl;

    return 0;
}

Output

242 188

Complexities

Time complexity

O(10^6+nlogn), where n is the length of the given array.

Reason: The precomputation takes O(9*9*1024*10) = O(10^6) time units. Then, using the lower bound function takes logn of time, and since we're doing it for all n numbers, in total, it takes O(nlogn) time. Thus, the total time complexity is O(10^6+nlogn).

Space complexity

O(10^10)

Reason: We're storing numbers till 10^10 in the set and the vector. Thus, the space complexity is O(10^10). All the other spaces are constant.

Check out this problem - Find Duplicate In Array

Must Read Lower Bound in C++

Frequently asked questions

  1. What is a next greater number of a number x?
    The nearest number greater than x is called the next greater number.
     
  2. What is the lower_bound() function?
    The lower_bound() function is a function that finds the number just greater than or equal to the given number from a list of sorted numbers.

Key Takeaways

In this article, we discussed how to find the next greater number formed with exactly two unique digits for each array element. One of the efficient ways to solve this problem requires the knowledge of bitmasking. You can learn more about this topic here.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!

Previous article
Maximize sum of LSBs of Bitwise OR of all possible N/2 pairs from given Array
Next article
Segmented Sieve
Live masterclass