HomeSoftware DevelopmentExamine if a Zero Array could be transformed to a given Array...

Examine if a Zero Array could be transformed to a given Array by incrementing some components with X^i


Given an array B, and two integers N, X (2 ≤ X ≤ 100). Initially, array arr has all its values as zero. The duty is to examine if array arr[] could be made equal to the given array B after performing the given operations:

  • Select a given place (p) (1 ≤ p ≤ n)
  • then improve arr[p] by Xi the place i is any optimistic integer.
  • Any ingredient could be chosen to be incremented any variety of instances (perhaps 0 instances).

Examples:

Enter: N = 3, X = 9
B[] = {0, 59059, 810}
Output: YES
Clarification: Initially all values in arr[] are  0. arr[] = {0, 0, 0}
Select arr[3], and add 92and 93 in two consecutive operations making it equal to 810. (arr[] = {0, 0, 810}).
Select arr[2] and add 95 to it making it 59059.
Thus now your complete array arr = {0, 59059, 810} which is the same as array b. 

Enter: N = 2, X = 10
B[] = {0, 0}
Output: YES
Clarification: The array initially is within the given stage. No must increment any worth.

 

Method: Because the query is coping with the ability of X, the very first thing to do is for every ingredient within the array B, discover its illustration in base X

  • When i = 0, then solely select some place and improve it with X0, which implies in all the components in array B just one can have items digit in base X and that will be equal to 1.
  • Equally for additional digits, as operations have been carried out with items digit as soon as, then transfer on to tens digit and additional.
  • Thus, if any place with the sum of digits better than 1, the reply might be “NO” as every place can solely be incremented by 1. else reply might be “YES”.

Beneath is the implementation of the above method:

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

  

int sod[100];

  

string remedy(vector<int>& B, int N, int X)

{

  

    

    for (int i = 0; i < 100; i++) {

        sod[i] = 0;

    }

    for (int i = 0; i < N; i++) {

        int t = 0;

  

        

        

        

        

        whereas (B[i] != 0) {

  

            

            sod[t] += B[i] % X;

            ++t;

            B[i] /= X;

        }

    }

  

    for (int i = 0; i < 100; i++) {

  

        

        

        

        if (sod[i] > 1) {

            return "NO";

        }

    }

    return "YES";

}

  

int foremost()

{

    vector<int> B = { 0, 59059, 810 };

    int N = 3, X = 9;

  

    

    cout << remedy(B, N, X);

    return 0;

}

Time Complexity: O(N * logX(a)), the place a is the utmost ingredient in array B.
Auxiliary Area: O(1)

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments