Find an integer in the given range that satisfies the given conditions

0 0 5 minutes read

Given two integers L and R where L ? R, the task is to find an integer K such that:

L ? K ? R.
All the digits of K are distinct.
The value of the expression (L – K) * (K – R) is maximum.

If multiple answers exist then choose the larger value for K.
Examples:

Input: L = 5, R = 10
Output: 8
Input: L = 50, R = 60
Output: 56

Approach: Iterate from L to R and for each value of K, check whether it contains all distinct digits and (L – K) * (K – R) is maximum. If two or more values give the same maximum value for the expression then choose the greater value for K.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 10;
 
// Function that returns true if x
// contains all distinct digits
bool distinctDigits(int x)
{
    bool present[MAX] = { false };
 
    while (x > 0) {
 
        // Last digit of x
        int digit = x % 10;
 
        // If current digit has
        // appeared before
        if (present[digit])
            return false;
 
        // Mark the current digit
        // to present
        present[digit] = true;
 
        // Remove the last digit
        x /= 10;
    }
 
    return true;
}
 
// Function to return the
// required value of k
int findK(int l, int r)
{
 
    // To store the maximum value
    // for the given expression
    int maxExp = INT_MIN;
    int k = -1;
    for (int i = l; i <= r; i++) {
 
        // If i contains all distinct digits
        if (distinctDigits(i)) {
            int exp = (l - i) * (i - r);
 
            // If the value of the expression
            // is also maximum then update k
            // and the expression
            if (exp >= maxExp) {
                k = i;
                maxExp = exp;
            }
        }
    }
 
    return k;
}
 
// Driver code
int main()
{
    int l = 50, r = 60;
 
    cout << findK(l, r);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
 
static int MAX = 10;
 
// Function that returns true if x
// contains all distinct digits
static boolean distinctDigits(int x)
{
    boolean []present = new boolean[MAX];
 
    while (x > 0) 
    {
 
        // Last digit of x
        int digit = x % 10;
 
        // If current digit has
        // appeared before
        if (present[digit])
            return false;
 
        // Mark the current digit
        // to present
        present[digit] = true;
 
        // Remove the last digit
        x /= 10;
    }
 
    return true;
}
 
// Function to return the
// required value of k
static int findK(int l, int r)
{
 
    // To store the maximum value
    // for the given expression
    int maxExp = Integer.MIN_VALUE;
    int k = -1;
    for (int i = l; i <= r; i++)
    {
 
        // If i contains all distinct digits
        if (distinctDigits(i)) 
        {
            int exp = (l - i) * (i - r);
 
            // If the value of the expression
            // is also maximum then update k
            // and the expression
            if (exp >= maxExp)
            {
                k = i;
                maxExp = exp;
            }
        }
    }
 
    return k;
}
 
// Driver code
public static void main(String[] args)
{
    int l = 50, r = 60;
 
    System.out.print(findK(l, r));
 
}
}
 
// This code is contributed by 29AjayKumar

Python 3

# Python3 implementation of the approach
import sys
MAX = 10
 
# Function that returns true if x
# contains all distinct digits
def distinctDigits(x):
    present = [False for i in range(MAX)]
 
    while (x > 0):
         
        # Last digit of x
        digit = x % 10
 
        # If current digit has
        # appeared before
        if (present[digit]):
            return False
 
        # Mark the current digit
        # to present
        present[digit] = True
 
        # Remove the last digit
        x = x // 10
 
    return True
 
# Function to return the
# required value of k
def findK(l, r):
     
    # To store the maximum value
    # for the given expression
    maxExp = -sys.maxsize - 1
    k = -1
    for i in range(l, r + 1, 1):
         
        # If i contains all distinct digits
        if (distinctDigits(i)):
            exp = (l - i) * (i - r)
 
            # If the value of the expression
            # is also maximum then update k
            # and the expression
            if (exp >= maxExp):
                k = i;
                maxExp = exp
    return k
 
# Driver code
if __name__ == '__main__':
    l = 50
    r = 60
 
    print(findK(l, r))
     
# This code is contributed by Surendra_Gangwar

C#

// C# implementation of the approach
using System;
 
class GFG
{
static int MAX = 10;
 
// Function that returns true if x
// contains all distinct digits
static bool distinctDigits(int x)
{
    bool []present = new bool[MAX];
 
    while (x > 0) 
    {
 
        // Last digit of x
        int digit = x % 10;
 
        // If current digit has
        // appeared before
        if (present[digit])
            return false;
 
        // Mark the current digit
        // to present
        present[digit] = true;
 
        // Remove the last digit
        x /= 10;
    }
    return true;
}
 
// Function to return the
// required value of k
static int findK(int l, int r)
{
 
    // To store the maximum value
    // for the given expression
    int maxExp = int.MinValue;
    int k = -1;
    for (int i = l; i <= r; i++)
    {
 
        // If i contains all distinct digits
        if (distinctDigits(i)) 
        {
            int exp = (l - i) * (i - r);
 
            // If the value of the expression
            // is also maximum then update k
            // and the expression
            if (exp >= maxExp)
            {
                k = i;
                maxExp = exp;
            }
        }
    }
    return k;
}
 
// Driver code
public static void Main(String[] args)
{
    int l = 50, r = 60;
 
    Console.Write(findK(l, r));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// javascript implementation of the approach    
var MAX = 10;
 
    // Function that returns true if x
    // contains all distinct digits
    function distinctDigits(x)
    {
        var present = new Array(MAX).fill(false);
 
        while (x > 0) {
 
            // Last digit of x
            var digit = x % 10;
 
            // If current digit has
            // appeared before
            if (present[digit])
                return false;
 
            // Mark the current digit
            // to present
            present[digit] = true;
 
            // Remove the last digit
            x = parseInt(x/10);
        }
 
        return true;
    }
 
    // Function to return the
    // required value of k
    function findK(l , r) {
 
        // To store the maximum value
        // for the given expression
        var maxExp = Number.MIN_VALUE;
        var k = -1;
        for (var i = l; i <= r; i++) {
 
            // If i contains all distinct digits
            if (distinctDigits(i)) {
                var exp = (l - i) * (i - r);
 
                // If the value of the expression
                // is also maximum then update k
                // and the expression
                if (exp >= maxExp) {
                    k = i;
                    maxExp = exp;
                }
            }
        }
 
        return k;
    }
 
    // Driver code
        var l = 50, r = 60;
        document.write(findK(l, r));
 
// This code is contributed by gauravrajput1
</script>

Output:

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 zambiatek!