가장 작은 좋은 자료

난이도 하드
자주 묻는 질문 구글
이진 검색 수학 조회수 94

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

모든 값에 대해 정수 n을 제공했다고 가정합니다. n 염기 k 좋은 염기 k> = 1 일 때 2입니다. 우리가 형식 번호 'n'. 문제 설명은 n의 가장 작은 좋은 밑을 찾아서 반환하도록 요구합니다. 형식입니다.

가장 작은 좋은 자료

String n = “15”
2

설명 : Base 15로 쓰여진 2는 1111입니다.

String n = “20”
19

설명 : Base 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의 모든 값에 대해 n-1이고 최소값은 2입니다.

결과적으로 우리는 각각의 가장 극단적 인 길이 묘사를 찾기 위해베이스를 줄여야합니다. 각 번호에 대해. 자릿수의 경우, 우리는 동등한 존경을 줄 수있는 기수가 존재하는지 찾으려고 할 것입니다. 주어진 값 = m,이 문제는 만족하는 정수 d와 n을 찾는 것입니다.

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

with 'i'는 배열을 순회 할 때마다 변경할 수있는 값입니다 (b가 최소화된다는 목표로).

방정식에 따라 우리는 항상 쌍으로 답을 얻습니다. 따라서 d1 = m-1. 따라서 목록에 삽입 한 답변의 가능한 값을 요약합니다. 값 (d1,…, dn)이 목록에 있으며 마지막 값을 가져옵니다. 우리는 1 + b + b ^ 2 + b ^ 3 +… + b ^ base의 다항식을 찾아야합니다.

가능한 모든 숫자의 값을 찾을 함수에 대한 후속 조치를 취합니다. 우리가 취한 루프는 최대 62 자리 숫자로 구성 될 수 있기 때문에 64까지이지만 63을 사용하면 오버플로가 발생합니다. 최소값을 찾을 때까지이 작업을 계속할 것이며 동시에 목록에 추가 할 것입니다. 따라서 우리는 가장 작은 염기를 찾고 마지막 염기를 가져 오기만하면됩니다.

암호

가장 작은 좋은베이스를 찾기위한 C ++ 코드

#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어디에 "엔" 문자열의 길이입니다.

공간 복잡성

O (N) 어디에 "엔" 문자열의 길이입니다.

균열 시스템 설계 인터뷰
Translate »