Count minimum steps to get the desired array

Introduction

Arrays are the backbone of every coding interview. As a result, a detailed understanding of the topic is required. However, there's no need to be alarmed. We're here to help, and today we'll take on the well-known interview question, "Count the smallest number of steps required to obtain the desired array." This is a straightforward array-based problem. Consider the question's problem statement: 'Count the smallest number of steps required to obtain the desired array.'

Understanding the Problem

Consider an array containing n entries, all of which have the value zero. The array may be used to conduct the following operations.

Incremental operations: Take one element from the array and add one to its value.

The values of all the array's items are doubled in the doubling operation.

The desired array target[] with n entries is handed to us. Calculate and return the fewest number of operations required to transform an array of zeros into the desired array.

Examples: 

Input: target[] = {2, 3}
Output: 4
We first increment both members by one (2 operations), then double the array (1 function) to get the target array from 0 to 0. Finally, increase the value of the second element (1 more function)

Input: target[] = {2, 1}
Output: 3
Doing the incremental operation twice on the first element and once on the second is one of the finest alternatives.

Input: target[] = {16, 16, 16}
Output: 7
As you can see, the final result is as follows. To begin, do an incremental operation on each element.
Then repeat the doubling procedure four times.
There are a total of 3+4 = 7 operations.

Keep in mind that the job counts the number of steps required to obtain the supplied goal array (not to convert zero arrays to the target array).

The objective is to go backward, converting the target to an array of zeros. Below are the steps.

First, we'll look at the target array.

Set the result to 0.

If all components are even, divide them by two and add one to the result.

Find all odd components and reduce them by one to make them even. and add 1 to the result for each reduction

Below is the implementation of the above algorithm. 

/* A C++ programme that counts the least number of operations required to obtain the provided target array. */
#include <bits/stdc++.h>
using namespace std;

// Returns the number of minimal operations required to convert a zero //array to a target array using increment and doubling. This function //counts by going backward in time, altering the target array to a zero // array.
int countMinOperations(unsigned int target[], int n)
{
// Initialize result (Count of minimum moves)
int result = 0;

// Keep looping while all elements of target
// don't become 0.
while (1)
{
// To store count of zeroes in current
// target array
int zero_count = 0;

int i; // To find first odd element
for (i=0; i<n; i++)
{
// If odd number found
if (target[i] & 1)
break;

// If 0, then increment zero_count
else if (target[i] == 0)
zero_count++;
}

// All numbers are 0
if (zero_count == n)
return result;

// All numbers are even
if (i == n)
{
// Divide the whole array by 2
// and increment result
for (int j=0; j<n; j++)
target[j] = target[j]/2;
result++;
}

// Make all odd numbers even by subtracting
// one and increment result.
for (int j=i; j<n; j++)
{
if (target[j] & 1)
{
target[j]--;
result++;
}
}
}
}

/* Driver program to test above functions*/
int main()
{
unsigned int arr[] = {16, 16, 16};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Minimum number of steps required to "
"get the given target array is "
<< countMinOperations(arr, n);
return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output : 

Minimum number of steps required to
get the given target array is 7

Time Complexity

O(N) where "N" is the elements in the array.

Space Complexity

O(N) where "N" is the elements in the array.