ಚಿಕ್ಕ ಗುಡ್ ಬೇಸ್


ತೊಂದರೆ ಮಟ್ಟ ಹಾರ್ಡ್
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಗೂಗಲ್
ಬೈನರಿ ಹುಡುಕಾಟ ಮಠ ಸ್ಟ್ರಿಂಗ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

ನ ಎಲ್ಲಾ ಮೌಲ್ಯಗಳಿಗೆ ನಾವು ಒಂದು ಪೂರ್ಣಾಂಕ n ನೀಡಿದ್ದೇವೆ ಎಂದು ಭಾವಿಸೋಣ n ಬೇಸ್ ಕೆ ಉತ್ತಮ ಬೇಸ್ k> = 1 ಆಗ 2 ಆಗಿರುತ್ತದೆ. ನಾವು ಒಂದು ನೀಡಿದ್ದೇವೆ ಎಂದು ಭಾವಿಸೋಣ ಸ್ಟ್ರಿಂಗ್ ಸ್ವರೂಪ-ಸಂಖ್ಯೆ 'n'. ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆಯು n ನ ಚಿಕ್ಕದಾದ ಉತ್ತಮ ನೆಲೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಮತ್ತು ಅದನ್ನು ಹಿಂತಿರುಗಿಸಲು ಕೇಳುತ್ತದೆ ಸ್ಟ್ರಿಂಗ್ ಸ್ವರೂಪ.

ಉದಾಹರಣೆ

ಚಿಕ್ಕ ಗುಡ್ ಬೇಸ್

String n = “15”
2

ವಿವರಣೆ: ಬೇಸ್ 15 ರಲ್ಲಿ ಬರೆದಾಗ 2 1111.

String n = “20”
19

ವಿವರಣೆ: ಬೇಸ್ 20 ರಲ್ಲಿ ಬರೆದಾಗ 19 11.

ಸಣ್ಣ ಉತ್ತಮ ಮೂಲ ಸಮಸ್ಯೆಗೆ ಅಲ್ಗಾರಿದಮ್

1. Set y to n-1.
2. Add the n-1 into the List.
3. From the i=2 to i< 63,
  1. Find out the val = pow of (y, 1.0 / i).
  2. From j=0 to j > - 3 and val + j > 1.
    1. Set d = val + j.
    2. And check if n % d is equal to 0.
      1. Find out this polynomial 1 + d + d ^ 2 + d ^ 3 + ... + d ^ i for d and up the current value of I and store into the sum.
    3. Check if this polynomial’s sum is equal to the n.
      1. Then add the value of d to the list.
4. Repeat the third process until the loop finishes.
5. Get the last element of the list and return that value.

ವಿವರಣೆ

ರಲ್ಲಿ n ಸಂಖ್ಯೆಯನ್ನು ನೀಡಲಾಗಿದೆ ಸ್ಟ್ರಿಂಗ್ ಸ್ವರೂಪ. ಪ್ರತಿ ಸಂಖ್ಯೆ n ಇದು ಬೇಸ್ನ ಗರಿಷ್ಠ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿದೆ n-1. ಮೌಲ್ಯವು 3 ರಿಂದ 10 ^ 18 ಕ್ಕೆ ಬದಲಾಗುವುದರಿಂದ, ಇದನ್ನು ಗರಿಷ್ಠ 64 ಅಂಕೆಗಳಲ್ಲಿ ಇಡಬಹುದಾಗಿದೆ. ಚಿಕ್ಕ ಬೇಸ್ 2 ಆಗಿರಬಹುದು ಮತ್ತು 63 ರವರೆಗೆ ಹೋಗಬಹುದು. ನಾವು ಲೆಕ್ಕ ಹಾಕಬಹುದಾದ ಗರಿಷ್ಠ ಬೇಸ್ n-1, n ನ ಯಾವುದೇ ಮೌಲ್ಯಕ್ಕೆ, ಮತ್ತು ಕನಿಷ್ಠ 2 ಆಗಿದೆ.

ಪ್ರತಿಯೊಂದರಲ್ಲೂ ಅತ್ಯಂತ ತೀವ್ರವಾದ ಉದ್ದದ ಚಿತ್ರಣವನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಾವು ಮೂಲವನ್ನು ಕಡಿಮೆ ಮಾಡಬೇಕಾಗಿದೆ. ಪ್ರತಿ ನಂ. ಅಂಕೆಗಳಲ್ಲಿ, ಗೌರವಕ್ಕೆ ಸಮಾನವಾದ ಬೇಸ್ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆಯೇ ಎಂದು ಕಂಡುಹಿಡಿಯಲು ನಾವು ಪ್ರಯತ್ನಿಸುತ್ತೇವೆ. ಮೌಲ್ಯ = ಮೀ ನೀಡಿದರೆ, ಈ ಸಮಸ್ಯೆ ಡಿ ಮತ್ತು ಎನ್ ಅನ್ನು ಪೂರೈಸುವ ಸಂಪೂರ್ಣ ಸಂಖ್ಯೆಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವುದು,

m = 1 + d + d ^ 2 + d ^ 3 +… + d ^ i.

'ನಾನು' ನೊಂದಿಗೆ ನಾವು ರಚನೆಯನ್ನು ದಾಟಿದಾಗಲೆಲ್ಲಾ ಬದಲಾಯಿಸಬಹುದಾದ ಮೌಲ್ಯವಾಗಿದೆ (ಬಿ ಅನ್ನು ಕಡಿಮೆ ಮಾಡುವ ಗುರಿಯೊಂದಿಗೆ).

ಸಮೀಕರಣದ ಪ್ರಕಾರ, ನಾವು ಯಾವಾಗಲೂ ಜೋಡಿಯಾಗಿ ಉತ್ತರವನ್ನು ಹೊಂದಿದ್ದೇವೆ ಅದರ ಪ್ರಕಾರ d1 = m-1. ಆದ್ದರಿಂದ ನಾವು ಪಟ್ಟಿಗೆ ಸೇರಿಸಿದ ಉತ್ತರದ ಸಂಭವನೀಯ ಮೌಲ್ಯಗಳನ್ನು ನಾವು ಒಟ್ಟುಗೂಡಿಸುತ್ತೇವೆ. ಮೌಲ್ಯಗಳು (ಡಿ 1,…, ಡಿಎನ್) ಪಟ್ಟಿಯಲ್ಲಿವೆ ಮತ್ತು ನಾವು ಕೊನೆಯ ಮೌಲ್ಯವನ್ನು ಪಡೆಯುತ್ತೇವೆ. ನಾವು 1 + b + b ^ 2 + b ^ 3 +… + b ^ ಬೇಸ್‌ನ ಬಹುಪದವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು.

ನಾವು ಒಂದು ಕಾರ್ಯವನ್ನು ಅನುಸರಿಸುತ್ತೇವೆ, ಅದರಿಂದ ನಾವು ಸಾಧ್ಯವಿರುವ ಪ್ರತಿಯೊಂದು ಸಂಖ್ಯೆಯ ಮೌಲ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯಲಿದ್ದೇವೆ. ನಾವು ತೆಗೆದುಕೊಂಡ ಲೂಪ್ 62 ರವರೆಗೆ ಇರುತ್ತದೆ ಏಕೆಂದರೆ ಈ ಸಂಖ್ಯೆಯನ್ನು 64 ಅಂಕೆಗಳವರೆಗೆ ರಚಿಸಬಹುದು, ಆದರೆ 63 ಸಾಧ್ಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುವುದರಿಂದ ಉಕ್ಕಿ ಹರಿಯುತ್ತದೆ. ನಾವು ಕನಿಷ್ಟ ಮೌಲ್ಯವನ್ನು ಕಂಡುಕೊಳ್ಳುವವರೆಗೂ ನಾವು ಇದನ್ನು ಮುಂದುವರಿಸುತ್ತೇವೆ ಮತ್ತು ಏಕಕಾಲದಲ್ಲಿ ನಾವು ಅದನ್ನು ಪಟ್ಟಿಗೆ ಸೇರಿಸಲಿದ್ದೇವೆ. ಆದ್ದರಿಂದ ನಾವು ಚಿಕ್ಕದಾದ ನೆಲೆಯನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು ಮತ್ತು ಕೊನೆಯದನ್ನು ಪಡೆದುಕೊಳ್ಳಬೇಕು.

ಕೋಡ್

ಚಿಕ್ಕದಾದ ಉತ್ತಮ ನೆಲೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಕೋಡ್

#include<iostream>
#include<string>
#include<vector>
#include<math.h>

using namespace std;

long getGetPolynomial(long, int);
string getMinGoodBase(string n)
{
    long x = stoi(n);
    vector<long> listt;
    listt.push_back(x-1);
    long y = x-1;
    for (int i = 2; i < 63; i++)
    {
        double val = pow(y, 1.0 / i);
        long value = (long) val;
        for (int j = 0; j > -3 && value + j > 1; j--)
        {
            long d = value + j;
            if (y % d == 0)
            {
                long poly = getGetPolynomial(d, i);

                if (poly == x)
                {
                    listt.push_back(d);
                }
            }
        }
    }
    long end = listt[listt.size() - 1];
    string out = to_string(end);
    return out;
}
long getGetPolynomial(long d, int n)
{
    long out = 1;
    long k = 1;
    for (int i = 0; i < n; i++)
    {
        k *= d;
        out += k;
    }
    return out;
}
int main()
{
    string num="15";
    cout<<getMinGoodBase(num);
}
2

ಚಿಕ್ಕದಾದ ಉತ್ತಮ ನೆಲೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜಾವಾ ಕೋಡ್

import java.util.ArrayList;
import java.util.List;

class GoodBase
{
    public static String getMinGoodBase(String n)
    {
        long x = Long.parseLong(n);
        List<Long> listt = new ArrayList<>();
        listt.add(x-1);
        long y = x-1;
        for (int i = 2; i < 63; i++)
        {
            double val = Math.pow(y, 1.0 / i);
            long value = (long) val;
            for (int j = 0; j > -3 && value + j > 1; j--)
            {
                long d = value + j;
                if (y % d == 0)
                {
                    long poly = getPolynomial(d, i);

                    if (poly == x)
                    {
                        listt.add(d);
                    }
                }
            }
        }
        long end = listt.get(listt.size() - 1);
        return end+"";
    }
    public static long getPolynomial(long d, int n)
    {
        long out = 1;
        long k = 1;
        for (int i = 0; i < n; i++)
        {
            k *= d;
            out += k;
        }
        return out;
    }
    public static void main(String args[])
    {
        String num="15";
        System.out.println(getMinGoodBase(num));
    }
}
2

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್2ಅಲ್ಲಿ “ಎನ್” ಇದು ಸ್ಟ್ರಿಂಗ್ನ ಉದ್ದವಾಗಿದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ಇದು ಸ್ಟ್ರಿಂಗ್ನ ಉದ್ದವಾಗಿದೆ.