Given an integer X and an array of strings str which represents numbers in any base ranging from [2, 36], the task is to check whether all the strings can be converted into X by assigning each string the desired base from 2 to 36, such that decimal base equivalent of the string is X.
Examples:Â Â
Input: str = {10000, 20, 16}, X = 16Â
Output: YesÂ
Explanation:Â
Every number in array is equal to 16 when converted to Decimal base, if following bases are selected:Â
(10000)2 = (16)10Â
(20)8 = (16)10Â
(16)10 = (16)10Input: str = {10100, 5A, 1011010}, X = 90Â
Output: YesÂ
Every number in array is equal to 90 when converted to Decimal base, if following bases are selected:Â
(10100)3 = (90)10Â
(5A)16 = (90)10Â
(1011010)2 = (90)10Â
 Â
Approach: The idea is to convert every number of the array into decimal-base by assigning it to a base from 2 to 36 and then check for each of the converted numbers that it is equal to X or not.Â
The step-by-step algorithm for the above approach is described below – Â
- Initialize the count to 0 for checking the count of numbers those are equal to X when converted.
- Run a loop to iterate over the numbers of the array and then for each of the numbers –Â
- Run another loop from 2 to 36 to assign base to the number and find the decimal equivalent of the number.
- If the decimal equivalent of the number is equal to X, then increment the count by 1 and break the loop for not assigning any other base to the same number.
- If the count of the numbers that are convertible to X is equal to the length of the array, then the array can correspond to the number X.
Below is the implementation of the above approach:
C++
// C++ implementation to check// whether array of strings// can correspond to a number XÂ
#include <bits/stdc++.h>using namespace std;Â
// Function to find the maximum // base possible for the number Nint val(char c){    if (c >= '0' && c <= '9')        return (int)c - '0';    else        return (int)c - 'A' + 10;}Â
// Function to find the decimal// equivalent of the numberint toDeci(string str, int base){    int len = str.size();    int power = 1;    int num = 0;    int i;    for (i = len - 1; i >= 0; i--) {                 // Condition to check if the        // number is convertible         // to another base        if (val(str[i]) >= base) {            return -1;        }        num += val(str[i]) * power;        power = power * base;    }    return num;}Â
// Function to check that the // array can correspond to a number X void checkCorrespond(vector<string> str,                                int x){                                         // counter to count the numbers    // those are convertible to X    int counter = 0;    int n = str.size();Â
    // Loop to iterate over the array    for (int i = 0; i < n; i++) {        for (int j = 2; j <= 36; j++) {                         // Convert the current string            // to every base for checking            // whether it will correspond            // to X from any base            if (toDeci(str[i], j) == x) {                counter++;                break;            }        }    }         // Condition to check if every    // number of the array can    // be converted to X    if (counter == n)        cout << "YES"            << "\n";    else        cout << "NO"            << "\n";}Â
// Driver Codeint main(){Â Â Â Â int x = 16;Â
    // The set of strings     // in base from [2, 36]    vector<string> str =         { "10000", "20", "16" };    checkCorrespond(str, x);    return 0;} |
Java
// Java implementation to check// whether array of Strings// can correspond to a number XÂ
class GFG{  // Function to find the maximum // base possible for the number Nstatic int val(char c){    if (c >= '0' && c <= '9')        return (int)c - '0';    else        return (int)c - 'A' + 10;}  // Function to find the decimal// equivalent of the numberstatic int toDeci(String str, int base){    int len = str.length();    int power = 1;    int num = 0;    int i;    for (i = len - 1; i >= 0; i--) {                  // Condition to check if the        // number is convertible         // to another base        if (val(str.charAt(i)) >= base) {            return -1;        }        num += val(str.charAt(i)) * power;        power = power * base;    }    return num;}  // Function to check that the // array can correspond to a number X static void checkCorrespond(String[] str,                                int x){                                          // counter to count the numbers    // those are convertible to X    int counter = 0;    int n = str.length;      // Loop to iterate over the array    for (int i = 0; i < n; i++) {        for (int j = 2; j <= 36; j++) {                          // Convert the current String            // to every base for checking            // whether it will correspond            // to X from any base            if (toDeci(str[i], j) == x) {                counter++;                break;            }        }    }          // Condition to check if every    // number of the array can    // be converted to X    if (counter == n)        System.out.print("YES"           + "\n");    else        System.out.print("NO"           + "\n");}  // Driver Codepublic static void main(String[] args){    int x = 16;      // The set of Strings     // in base from [2, 36]    String[] str =         { "10000", "20", "16" };    checkCorrespond(str, x);}}Â
// This code contributed by PrinciRaj1992 |
Python3
# Python3 implementation to check# whether array of strings# can correspond to a number XÂ
# Function to find the maximum # base possible for the number Ndef val(c):    if (c >= '0' and c <= '9'):        return int(c)    else:        return c - 'A' + 10         # Function to find the decimal# equivalent of the numberdef toDeci(strr, base):         lenn = len(strr)    power = 1    num = 0    for i in range(lenn - 1, -1, -1):                 # Condition to check if the        # number is convertible         # to another base        if (val(strr[i]) >= base):            return -1                 num += val(strr[i]) * power        power = power * base         return numÂ
Â
# Function to check that the # array can correspond to a number X def checkCorrespond(strr, x):         # counter to count the numbers    # those are convertible to X    counter = 0    n = len(strr)         # Loop to iterate over the array    for i in range(n):        for j in range(2,37):                         # Convert the current string            # to every base for checking            # whether it will correspond            # to X from any base            if (toDeci(strr[i], j) == x):                counter += 1                break                 # Condition to check if every    # number of the array can    # be converted to X    if (counter == n):        print("YES")    else:        print("NO")Â
# Driver Codex = 16Â
# The set of strings # in base from [2, 36]strr = ["10000", "20", "16"]checkCorrespond(strr, x)Â
# This code is contributed by shubhamsingh10 |
C#
// C# implementation to check// whether array of Strings// can correspond to a number Xusing System;Â
class GFG{   // Function to find the maximum // base possible for the number Nstatic int val(char c){    if (c >= '0' && c <= '9')        return (int)c - '0';    else        return (int)c - 'A' + 10;}   // Function to find the decimal// equivalent of the numberstatic int toDeci(String str, int Base){    int len = str.Length;    int power = 1;    int num = 0;    int i;    for (i = len - 1; i >= 0; i--) {                   // Condition to check if the        // number is convertible         // to another base        if (val(str[i]) >= Base) {            return -1;        }        num += val(str[i]) * power;        power = power * Base;    }    return num;}   // Function to check that the // array can correspond to a number X static void checkCorrespond(String[] str,                                int x){                                           // counter to count the numbers    // those are convertible to X    int counter = 0;    int n = str.Length;       // Loop to iterate over the array    for (int i = 0; i < n; i++) {        for (int j = 2; j <= 36; j++) {                           // Convert the current String            // to every base for checking            // whether it will correspond            // to X from any base            if (toDeci(str[i], j) == x) {                counter++;                break;            }        }    }           // Condition to check if every    // number of the array can    // be converted to X    if (counter == n)        Console.Write("YES"           + "\n");    else        Console.Write("NO"           + "\n");}   // Driver Codepublic static void Main(String[] args){    int x = 16;       // The set of Strings     // in base from [2, 36]    String[] str =         { "10000", "20", "16" };    checkCorrespond(str, x);}}Â
// This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation to check// whether array of Strings// can correspond to a number XÂ
// Function to find the maximum // base possible for the number Nfunction val(c){    if (c >= '0' && c <= '9')        return c - '0';    else        return c - 'A' + 10;}  // Function to find the decimal// equivalent of the numberfunction toDeci(str, base){    let len = str.length;    let power = 1;    let num = 0;    let i;    for (i = len - 1; i >= 0; i--) {                  // Condition to check if the        // number is convertible         // to another base        if (val(str[i]) >= base) {            return -1;        }        num += val(str[i]) * power;        power = power * base;    }    return num;}  // Function to check that the // array can correspond to a number X function checkCorrespond(str, x){                                          // counter to count the numbers    // those are convertible to X    let counter = 0;    let n = str.length;      // Loop to iterate over the array    for (let i = 0; i < n; i++) {        for (let j = 2; j <= 36; j++) {                          // Convert the current String            // to every base for checking            // whether it will correspond            // to X from any base            if (toDeci(str[i], j) == x) {                counter++;                break;            }        }    }          // Condition to check if every    // number of the array can    // be converted to X    if (counter == n)        document.write("YES"           + "<br/>");    else        document.write("NO"           + "<br/>");}Â
// Driver Code         let x = 16;      // The set of Strings     // in base from [2, 36]    let str =         [ "10000", "20", "16" ];    checkCorrespond(str, x);         </script> |
Output:Â
YES
Â
Performance Analysis:Â
- Time Complexity: O(N).
- Auxiliary Space: 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!
