Verilən Array almaq üçün minimum addımları sayın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Fanatics Kahin
GeyimBaxılıb 416

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Verilən massiv problemini əldə etmək üçün minimum addımları sayarkən, n elementi olan bir giriş sıra hədəfi verdik, minimum ölçülü dizini [] bütün sıfırlarla hədəf [] -ə çevirmək üçün minimum əməliyyat sayını hesablamalıyıq.

Əməliyyatlar

a) Bir elementi 1 artırmaq bir əməliyyatdır.
b) Bütün elementləri ikiqat artırmaq bir əməliyyatdır.

misal

a) Giriş: hədəf massivi -> [1,1]

Çıxış: 2,
[1, 0] -> 0 əməliyyat əldə etmək üçün [1, 1] 'dəki hər iki element üçün 2 artım.

b) Giriş: hədəf massivi -> [2, 2]

Çıxış: 3,
[1, 0] -> 0 əməliyyat əldə etmək üçün [1, 1] 'dəki hər iki element üçün 2 artım,
[1, 1] -> 2 əməliyyatı əldə etmək üçün [2, 1] içindəki bütün elementləri ikiqat artırın
Cəmi = 3

c) Giriş: hədəf massivi -> [2,3]

Çıxış: 4,
[1, 0] -> 0 əməliyyat əldə etmək üçün [1, 1] 'dəki hər iki element üçün 2 artım,
[1, 1] -> 2 əməliyyatı əldə etmək üçün [2, 1] içindəki bütün elementləri ikiqat artırın
[1, 2] -> 2 əməliyyat əldə etmək üçün [2, 3] -də ikinci element üçün 1 artım,
Cəmi = 4

d) Giriş: hədəf sıra -> [4, 4, 5]

Çıxış: 6,
[1, 0, 0] -> 0 əməliyyat əldə etmək üçün [1, 1, 1] içindəki bütün elementlər üçün 3 artım,
[1, 1, 1] -> 2 əməliyyatı əldə etmək üçün [2, 2, 1] içindəki bütün elementləri ikiqat artırın
[2, 2, 2] -> 4 əməliyyatı əldə etmək üçün [4, 4, 1] içindəki bütün elementləri ikiqat artırın
[1, 3, 4] - də 4-cü elementdə 4 artım [4, 4, 5] -> 1 əməliyyat,
Cəmi = 6

Alqoritm

Əsas fikir: Verilən massivin sıfır cərgəyə çevrilməsindəki addımların sayını hesablayın. Bu, sıfır cərgəni hədəf massivinə çevirməklə eynidir

1. Minimum əməliyyat sayını tapmaq üçün bir funksiya yaradın.

2. Minimum hərəkətləri başladın (min_moves) = 0

3. Dizidəki sıfır sayını sayın, sıfır sayı massivin ölçüsünə bərabərdirsə, min_moves qayıdır.

4. Tək nömrələri tapmaq üçün massivdən keçin, əgər tək bir nömrə dəyəri 1-ə endirsə, min_moves-i 1 artırın və bütün elementlər bunu edənə qədər irəliləyin.

5. Bütün elementlər bərabərdirsə, bütün elementləri 2-yə bölün və min_moves-i yalnız 1 dəfə artırın.

6. massivdəki bütün elementlər sıfır olana qədər buna davam edin.

7. Verilən giriş hədəf massivində bu funksiyanı çağırın, yazdırın. Bu addımların minimum sayıdır.

Həyata keçirilməsi

C ++ Proqramı

/* C++ program to count minimum number of operations
   to get the given target array */
#include <bits/stdc++.h>
using namespace std;
 
//we make the target array to zero array
//count the number of moves
//it is nothing but converting zero array into target array
int Minimum_Operations(unsigned int target[], int n)
{
    int min_moves = 0;
    //Till all elements become zero
    while(1)
    {
        //count of zeroes
        int zeroes = 0;
        int i;
        // i is index of first odd number
        for(i=0; i<n; i++)
        {
            if (target[i] & 1)// odd number
                {
                  break;
                }
            else if (target[i] == 0)//zeroes in target array
                {
                  zeroes++;
                }
        }
        //return moves when all the elements in target array are zero
        if (zeroes == n)
          {
            return min_moves;
          }
        //if i = n odd number is not found in the array
        // so all are even
        //Divide by two and increment 1 move
        if (i == n)
        {
            for (int j=0; j<n; j++)
            {
               target[j] = target[j]/2;
            }
            min_moves++;
        }
 
        //if odd number found decrese it by 1 
        // increment moves by 1
        for (int j=i; j<n; j++)
        {
           if (target[j] & 1)
           {
              target[j]--;
              min_moves++;
           }
        }
    }
}
 
//main function
int main()
{
    unsigned int arr[] = {4, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout <<"Minimum steps to get target array is: " << Minimum_Operations(arr, n);
    return 0;
}
Minimum steps to get target array is: 6

Java Proqramı

import java.util.Scanner;
class sum
{
    //we make the target array to zero array
    //count the number of moves
    //it is nothing but converting zero array into target array
    public static int Minimum_Operations( int target[], int n)
    {
        int min_moves = 0;
        //Till all elements become zero
        while(1==1)
        {
            //count of zeroes
            int zeroes = 0;
            int i;
            // i is index of first odd number
            for(i=0; i<n; i++)
            {
                if ((target[i]&1)== 1)// odd number
                    {
                      break;
                    }
                else if(target[i] == 0)//zeroes in target array
                    {
                      zeroes++;
                    }
            }
            //return moves when all the elements in target array are zero
            if (zeroes == n)
              {
                return min_moves;
              }
            //if i = n odd number is not found in the array
            // so all are even
            //Divide by two and increment 1 move
            if (i == n)
            {
                for (int j=0; j<n; j++)
                {
                   target[j] = target[j]/2;
                }
                min_moves++;
            }

            //if odd number found decrese it by 1 
            // increment moves by 1
            for (int j=i; j<n; j++)
            {
               if((target[j] & 1)==1)
               {
                  target[j]--;
                  min_moves++;
               }
            }
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        System.out.println("Minimum steps to get target array is: "+ Minimum_Operations(a,n)); 
    }
}
3
4 4 5
6
Crack Sistemi Dizayn Müsahibələri
Translate »