عد الخطوات الدنيا للحصول على الصفيف المطلوب المحدد


مستوى الصعوبة متوسط
كثيرا ما يطلب في عاصمة واحدة سيتريكس Coursera سينوبسيس زيكوس
مجموعة الرياضيات

المشكلة بيان

افترض أن لديك مصفوفة تحتوي على عدد صحيح 0 فقط مثل جميع عناصرها. ضع في اعتبارك أنك حصلت على مجموعة من الطول n وجود جميع 0s التي يتعين علينا فيها تحويل 0s إلى المصفوفة المطلوبة المحددة. يمكننا تسمية المصفوفة المطلوبة باسم المطلوب مجموعة مصفوفة. وبالتالي نحن بحاجة إلى حساب الحد الأدنى من الخطوات للحصول على المصفوفة المطلوبة المحددة. هذا هو معرفة الحد الأدنى لعدد العمليات الممكنة التي تحتاج إلى تغيير الصفيف الصفري إلى الصفيف المطلوب المحدد. يمكننا القيام بالعمليات التالية فقط.

  1. عملية مضاعفة: إما أن نضاعف قيمة عنصر مصفوفة ، أو
  2. عمليات تزايدية: يمكننا زيادة عنصر قيمة المصفوفة بمقدار 1.

 

مثال

desiredArr[] = {1, 2}
3

التفسير:

تحويل {0,0،XNUMX} إلى المطلوب مجموعة

  • زيادة قيمة العنصر بمقدار 1 ← (عمليتان)
  • زيادة العنصر الثاني بمقدار 1 → (عملية إضافية واحدة)
  • هذا يجعله إجمالي 3 عمليات.

 

desiredArr[] = {4, 2}
4

التفسير:

  • قم بزيادة كل من قيم العنصر بمقدار 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.

يمكننا أخذ المثال على النحو التالي arr [] = {4، 2} ، وعلينا أيضًا أن نفترض أن لدينا مصفوفة من 0s. لذلك علينا أولاً زيادة قيمة العناصر بمقدار 1 ، لذلك نحسب عمليتين. الآن لدينا {2، 1} كمصفوفة. نقوم الآن بمضاعفة المصفوفة بأكملها بحيث نحصل على إجمالي {1 و 2} و 2 عمليات. نحتاج فقط إلى أن يكون لدينا 3 في المركز الأول. لذلك ، قمنا بمضاعفة هذه القيمة وحتى الآن قمنا بأربع عمليات في المجموع. 4 هو الحد الأدنى لعدد الخطوات لدينا للحصول على الصفيف المطلوب.

كانت هذه مجرد طريقة بديهية للفهم. لكن بدلاً من القيام بذلك ، سنقوم بتحويل مصفوفة الإدخال إلى مصفوفة من 0 ثانية. لذلك ، للقيام بذلك ، نقوم بعمل معاكس لعمليات معينة. نحن ننقص العناصر إذا كانت فردية ، وبمجرد أن نحصل على جميع عناصر المصفوفة زوجيًا. نقسم كل عنصر (عناصر في المصفوفة) على 2 وهذا يعد عملية واحدة. مثل على سبيل المثال [4,2،2,1] -> [2,0،1,0] -> [0,0،XNUMX] -> [XNUMX،XNUMX] -> [XNUMX،XNUMX] يحصل على الرغم من التغييرات كما هو موضح.

ملاحظة

تستخدم هذه التقنية في مشاكل أخرى أيضًا. تحويل عدد صحيح من 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 (ن) أين "ن" هو عدد العناصر في الصفيف.

تعقيد الفضاء

O (ن) أين "ن" هو عدد العناصر في الصفيف.