Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Understanding the Problem
2.1.
Time Complexity
2.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
Why is it efficient to use an array?
3.2.
What are the limitations of an array?
3.3.
Which is a faster array or a linked list?
3.4.
What is the advantage of using an array to match a value in a range of values?
3.5.
How do you overcome the limitations of an array?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Count minimum steps to get the desired array

Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

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;
}

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.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

Why is it efficient to use an array?

Because all components are stored in contiguous memory locations, arrays are particularly efficient at accessing values. As a result, the computer knows exactly where to look for the data you've requested.

What are the limitations of an array?

The resulting array will be homogenous. Only integer values can be saved in an integer array, whereas only floating values may be stored in a float array, and only characters can be stored in a character array. As a result, no array may include values of two different data types.

Which is a faster array or a linked list?

Because random access is not permitted, linked lists take longer to search than arrays. Unlike arrays, which allow you to search for elements by index, linked lists need iteration.

What is the advantage of using an array to match a value in a range of values?

You'll have enough array elements, or at the very least, be less likely to run out. What are the benefits of using an array to match a value in a range? The items of a ten-element array are accessed using subscripts 1 through 10.

How do you overcome the limitations of an array?

Finally, by paying a more significant memory cost and sacrificing constant-time random access, the linked list overcomes the array's flexibility constraint. Answer: Linked lists provide the following advantages over arrays: A linked list makes storing data of various sizes easier.

Conclusion

So that's the end of the article, Count minimum steps to get the desired array.

After reading about the Count minimum steps to get the desired array., are you not feeling excited to read/explore more articles on the topic of data structures? Don't worry; Coding Ninjas has you covered.

However, you may want to pursue our premium courses to give your job an advantage over the competition!

Recommended Readings:

Recommended problems -

 

With our Coding Ninjas Studio Guided Path, you may learn about Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and more! If you wish to test your coding abilities, check out the mock test series and enter the contests on Coding Ninjas Studio.However, suppose you've just started school and are looking for answers to concerns raised by digital behemoths such as Amazon, Microsoft, Uber, and others, as part of your placement preparations. In that case, you must evaluate the obstaclesinterview experiences, and interview package in this case. Please vote for our blogs if you find them valuable and exciting.

Happy studying!

Previous article
Sorting Array Except Elements in a Subarray
Next article
Minimum swaps required to bring all elements together less than or equal to a given number
Live masterclass