How to distribute 'n' items in an 'M' sized array such that the elements get dis-CodePudding

Suppose I have an array of size 100. Initially, let's assume that all the elements have a value of 0. Now, let's say I want to insert 60 elements such that the elements get filled evenly. I don't want all the elements to be filled from arr[0] to arr[59]. Rather, I want the whole array to be filled in such a way that the array looks filled. What algorithm can I use to achieve this?

For eg-

I have 5 elements to be filled (let's say with 1) in an array of size 10. Then the array should look like this:

[1,0,1,0,1,0,1,0,1,0]

In the case of 3 elements,

[1,0,0,0,1,0,0,0,1,0]

Is there any smart way to do this dynamically?

CodePudding user response：

You would need to find the right gap length to evenly fill it. For this, we binary search the correct gap which most evenly fills the gap such that the no. of 1's to be supposedly filled doesn't go out of the array bounds.

In the case where no. of ones to be filled is greater than half of the array size, we fill it with as even gaps of length 2 as much as possible and fill the remaining ones adjacent to each other.

function solve(arraySize, oneCount) {
  let newArray = Array(arraySize).fill(0);
  let low = 0,
    high = arraySize;
  let gap = 0;
  while (low <= high) {
    let mid = (low   high) >> 1;
    if (mid * (oneCount - 1) < arraySize) {
      gap = mid;
      low = mid   1;
    } else {
      high = mid - 1;
    }
  }

  let needsEvenDivision = oneCount > (arraySize >> 1) && gap === 1;
  gap = needsEvenDivision ? 2 : gap;
  let idx = 0;
  while (idx < arraySize && oneCount > 0) {
    newArray[idx] = 1;
    oneCount--;
    if (needsEvenDivision && arraySize - idx - 2 < oneCount) gap = 1;
    idx  = gap;
  }

  return newArray;
}

console.log(solve(4, 2));
console.log(solve(10, 4));
console.log(solve(10, 7));

CodePudding user response：

The problem is like:

There is a 60mm long rubber with a scale every 1mm. Where is the position of each scale when this rubber is stretched to a length of 100 mm?

int main(void)
{
    constexpr int M= 10;
    constexpr int n = 5;

    //initially all 0
    int Array[M] = { 0 };

    //Calclate where the ith element of the n elements should go in the result array
    for( int i=0; i<n;   i )
    {
        int idx = (int)std::round( (double)i * M / n);
        Array[idx] = 1;
    }

    //Show Result
    for( auto a : Array ){  std::cout << a << " ";  }
    std::cout << std::endl;

    return 0;
}

CodePudding user response：

Here is something you can do

function populateArray(arraySize, arrayElements) {
const newArray = [];
if (arraySize >= arrayElements) {
    const parts = Math.ceil(arraySize / arrayElements);
    for (let i = 0; i < arraySize; i  ) {
        if (i % parts == 0) {
            newArray.push(1);
        } else {
            newArray.push(0);
        }
    }
    return newArray;
}
return "Invalid array Size";
}
console.log(populateArray(10, 3));