C++で指定された目的の配列を取得するための最小ステップ数を数えます

数字を含む配列target[]が与えられます。次の2つの操作のみを使用して、すべてゼロ[0,0,0,0…]の配列をターゲットに変換できる最小ステップを見つける必要があります-

• インクリメント操作-すべての要素を1ずつインクリメントできます。各インクリメント操作は、ステップごとに個別にカウントできます。 （n要素のn増分の場合steps =n）

• 倍増操作-配列全体が倍増します。すべての要素について、1回カウントされます。 （各2倍化操作は、すべての要素の値を2倍にし、ステップごとに1としてカウントします

目標は、目標に到達するための最小ステップ数を見つけることです。たとえば、[0,0,0]は最小3ステップで[1,1,1]になり（すべての要素の増分操作によって）、もう1回の倍増操作で[2,2,2]になり、今回は合計4ステップになります（ 3増分、1倍増）。

入力

target[]= { 1,2,2,3 }

出力

Minimum steps to reach target from {0,0,0,0} : 6

説明

最初は{0,0,0,0}

3つのインクリメント操作{0,1,1,1}//インクリメントは個別に発生します

1つのダブリング操作{0,2,2,2}//すべての要素でダブリングが発生します

2インクリメント操作{1,2,2,3}

総歩数=3+ 1 + 2 =6

入力

target[]= { 3,3,3 }

出力

Minimum steps to reach target from {0,0,0} : 7

説明

最初は{0,0,0}

3つのインクリメント操作{1,1,1}//インクリメントは個別に発生します

1倍増操作{2,2,2}//すべての要素で倍増が発生します

3インクリメント操作{3,3,3}

合計ステップ数=3+ 1 + 3 =7

以下のプログラムで使用されているアプローチは次のとおりです

• 整数配列target[]は、到達するターゲット要素を格納します。

• 関数minSteps（int target []、int n）は、ターゲット配列とその長さ「n」を入力として受け取り、すべてゼロからターゲットに到達するための最小ステップ数を返します。

• 可変カウントは、ステップカウントを格納するために使用されます。最初は0です。

• 変数maxは、最初はtarget[0]である最上位の要素を格納するために使用されます。

• 変数posは、見つかったmaxのインデックス（最初は0）を格納するために使用されます。

• target []配列にすべてゼロがある場合、ステップは不要であるため、0を返します。 （for（i =0; i

• このアプローチでは、target[]からすべてのゼロに到達します。

• 奇数の要素から1を引いて、すべての要素を偶数にします。各減算のインクリメントカウント（インクリメント操作と同じ）

• これで、すべて偶数になりました。

• また、同じループ内の最大値とその位置を見つけて、最大値と位置を初期化します。

• ここで、最大値が1にならないまで、配列全体を2で除算し始めます。いずれかの数値が奇数になった場合は、1をデクリメントしてカウントを増やし、全体の除算操作でカウントを1回インクリメントします。

• 最後に、すべての要素が0または1になります。すべての要素が0になり、カウントが再び増加します。

• カウントに存在するステップとして結果を返します。

例

#include <bits/stdc++.h>
using namespace std;
int minSteps(int target[],int n){
   int i;
   int count=0;
   int max=target[0];
   int pos=0;
   for(i=0;i<n;i++)
      if(target[i]==0)
         count++;
      //if all are zeros, same as target
      if(count==n)
         return 0;
         count=0;
         //make all even by sbtracting 1
      for(i=0;i<n;i++){
         if(target[i]%2==1){
            target[i]=target[i]-1;
            count++;
      }
      //find max value and its position
      if(target[i]>=max){
         max=target[i];
         pos=i;
      }
   }
   //diving by 2 till all elements are 1 and increase count once
   while(target[pos]!=1){
      for(i=0;i<n;i++){
         if(target[i]%2==1){
             target[i]=target[i]-1;
            count++;
      }
      target[i]=target[i]/2;
   }
   count++;
}
//whole array is {1} make zeroes and increase count
while(target[pos]!=0){
   for(i=0;i<n;i++){
      if(target[i]!=0){
         target[i]=target[i]-1;
         count++;}
      }
   }
   return count;
}
int main(){
   int target[]={15,15,15};
   cout<<"\nMinimum steps to get the given desired array:"<<minSteps(target,3);
   return 0;
}

出力

Minimum steps to get the given desired array:15