Check whether an array of strings can correspond to a particular number X

0 0 7 minutes read

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)₂ = (16)₁₀
(20)₈ = (16)₁₀
(16)₁₀ = (16)₁₀

Input: 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)₃ = (90)₁₀
(5A)₁₆ = (90)₁₀
(1011010)₂ = (90)₁₀

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 N
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 number
int 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 Code
int 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 N
static 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 number
static 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 Code
public 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 N
def val(c):
    if (c >= '0' and c <= '9'):
        return int(c)
    else:
        return c - 'A' + 10
         
# Function to find the decimal
# equivalent of the number
def 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 Code
x = 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 X
using System;
 
class GFG{
   
// Function to find the maximum 
// base possible for the number N
static 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 number
static 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 Code
public 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 N
function val(c)
{
    if (c >= '0' && c <= '9')
        return c - '0';
    else
        return c - 'A' + 10;
}
  
// Function to find the decimal
// equivalent of the number
function 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 zambiatek!