주어진 원하는 배열을 얻기 위해 최소 단계를 계산합니다.


난이도 중급
자주 묻는 질문 자본 하나 시트릭스 Coursera Synopsys 자이쿠스
배열 수학

문제 정책

모든 요소로 정수 0 만 포함하는 배열이 있다고 가정합니다. 길이 배열이 주어집니다. n 0을 주어진 필수 배열로 변환해야하는 모든 0이 있습니다. 필요한 배열의 이름을 원하는 도착 정렬. 따라서 주어진 원하는 배열을 얻으려면 최소 단계를 계산해야합니다. 즉, 제로 배열을 주어진 필수 배열로 변경하는 데 필요한 최소 작업 수를 알아내는 것입니다. 다음 작업 만 수행 할 수 있습니다.

  1. 두 배 연산 : 배열의 요소 값을 두 배로 늘리거나
  2. 증분 연산 : 배열 값의 요소를 1 씩 늘릴 수 있습니다.

 

desiredArr[] = {1, 2}
3

설명 :

{0,0}을 원하는 값으로 변환 정렬

  • 두 요소의 값을 1 씩 증가 → (2 회)
  • 두 번째 요소를 1 씩 증가 → (한 번 더 작업)
  • 총 3 개의 작업이됩니다.

 

desiredArr[] = {4, 2}
4

설명 :

  • 두 요소의 값을 1 씩 증가 → (2 회)
  • 모든 배열 요소의 값을 두 배로 → (1 연산)
  • 첫 번째 요소 두 배 → (1 개 더 작업)
  • 총 4 개의 작업이됩니다.

 

주어진 원하는 배열을 얻기 위해 최소 단계를 계산하는 알고리즘

1. Get the desiredArr array.
2. Set output as 0.
3. Check if all the elements given are even, then divide all the elements by 2 and increase the output by 1.
4. Get all of the odd elements, make them even by decrease their value by 1.
5. For every decrement, increase the value of output by 1.
6. We get all zeros in desiredArr array, after completing all the steps.
7. Return output.

 

설명

우리는 입력 배열을 제공했고 또한 요소 0만을 포함하는 배열이 있다고 가정합니다. 여기서 주어진 원하는 배열을 얻기 위해 최소 단계를 계산하는 작업을 수행하려고합니다. 수행 된 작업은 주어진 지침을 충족해야합니다. 즉, 주어진 지침을 충족하는 작업 만 수행하는 필수 배열을 만듭니다.

첫 번째 작업은 배열의 요소 값을 1 씩 늘릴 수 있다는 것입니다. 이것은 n 개의 작업으로 계산됩니다. 즉, n 개의 요소 값을 1 씩 늘린다는 의미입니다. 두 번째 작업은 요소가 아닌 전체 배열을 두 배로 늘리는 것입니다. 전체 배열에 2를 곱합니다. 따라서 전체 배열에 2를 곱하면 1 개의 연산이 완료됩니다. 따라서 두 값을 모두 1 씩 늘린 다음 배열을 두 배로 늘려 작업 수를 세면 총 작업 수가 3이라는 의미입니다.

예를 arr [] = {4, 2}로 사용할 수 있으며 또한 0의 배열이 있다고 가정해야합니다. 따라서 먼저 요소의 값을 1 씩 늘려야하므로 2 개의 연산을 계산합니다. 이제 배열로 {1, 1}이 있습니다. 이제 전체 배열을 두 배로 늘려서 총 {2, 2} 및 3 개의 연산을 얻습니다. 첫 번째 위치에 4 ​​개만 있으면됩니다. 이를 위해 우리는 그 값을 두 배로 늘렸고 지금까지 총 4 개의 작업을 수행했습니다. 4는 원하는 배열을 얻기위한 최소 단계 수입니다.

이것은 이해의 직관적 인 방법이었습니다. 그러나 이렇게하는 대신 입력 배열을 0 배열로 변환 할 것입니다. 따라서이를 수행하기 위해 주어진 작업과 반대되는 작업을 수행합니다. 요소가 홀수이면 감소하고 일단 배열의 모든 요소가 짝수이면 요소를 감소시킵니다. 각각 (배열의 요소)을 2로 나누면 단일 작업으로 계산됩니다. 예를 들어 [4,2]-> [2,1]-> [2,0]-> [1,0]-> [0,0]은 다음과 같이 변경됩니다.

주의 사항

이 기술은 다른 문제에서도 사용됩니다. 유사한 명령어를 사용하여 정수 A를 B로 변환하는 것도 그중 하나입니다. A를 1로 줄이거 나 A에 2를 곱할 수 있습니다. 다시 한 번 B를 A로 변환하려고합니다. 이는 제안 된 문제에 대한 다른 솔루션에 비해 훨씬 쉽습니다.

 

주어진 원하는 배열을 얻기 위해 최소 단계를 계산합니다.

주어진 원하는 배열을 얻기 위해 최소 단계를 계산하는 코드

C ++ 코드

#include<iostream>
using namespace std;

int getMinimumOperations(unsigned int desiredArr[], int n)
{
    int output = 0;
    while (1)
    {
        int zeroArrCnt= 0;

        int i;
        for (i=0; i<n; i++)
        {
            if (desiredArr[i] & 1)
                break;

            else if (desiredArr[i] == 0)
                zeroArrCnt++;
        }
        if (zeroArrCnt== n)
            return output;
        if (i == n)
        {
            for (int j=0; j<n; j++)
                desiredArr[j] = desiredArr[j]/2;
            output++;
        }
        for (int j=i; j<n; j++)
        {
            if (desiredArr[j] & 1)
            {
                desiredArr[j]--;
                output++;
            }
        }
    }
}
int main()
{
    unsigned int arr[] = {4, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout <<getMinimumOperations(arr, n);
    return 0;
}
4

자바 코드

class minimumSteps
{
    public static int getMinimumOperations(int arr[],int n)
    {
        int output = 0;
        while (true)
        {

            int zeroArrCnt= 0;

            int i;
            for (i=0; i<n; i++)
            {
                if (arr[i] % 2 == 1)
                    break;
                else if (arr[i] == 0)
                    zeroArrCnt++;
            }
            if (zeroArrCnt== n)
                return output;

            if (i == n)
            {
                for (int j=0; j<n; j++)
                    arr[j] = arr[j]/2;
                output++;
            }
            for (int j=i; j<n; j++)
            {
                if (arr[j] %2 == 1)
                {
                    arr[j]--;
                    output++;
                }
            }
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {4, 2} ;
        System.out.println(getMinimumOperations(arr,arr.length));
    }
}
4

복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.