CODEWITHSUNDEEP
javaarraysalgorithmarraylist
Aleksandr
Aleksandr

Reputation: 11

Redistributing the array

I'm trying to redistribute the array of Integers. The aim is: I have an array, let it be {2_000_000_000, 0}.

I need:

  1. Find the max element of the array.
  2. Save it to the temp variable.
  3. Set the maximum element = 0.
  4. Distribute the max element between rest ones, beginning from the next of max element. If the end of array is reached, I need to start from the beginning.

My code below:

for (int i = 0; i < data.size(); i++){  //Looking for max element
    if (data.get(i) > max){             //of the array
        max = data.get(i);              //Save max element
        index = i;                      //Save the index of max element
    }
}
data.set(index, 0);              //Set max element = 0
if (index == data.size()){       //In case of end of array
    initPos = 0;                 //position is the beginning
}else {
    initPos = index + 1;         //If no the end - pos is the next
}

while (max > 0){                    //This block of code looks have
    if (initPos == data.size()){    //a small speed
        initPos = 0;
    }
    int oldVal = data.get(initPos);
    oldVal++;
    data.set(initPos, oldVal);
    max--;
    initPos++;                                 
}

So the question is: the code while(max > 0)... seems to be working slowly.

Do I need to use different structures instead of ArrayList to speed-up the distribution process?

Upvotes: 0

Views: 214

Answers (1)

Cid
Cid

Reputation: 15247

Instead of looping max times, I would calculate the amount to distribute to each other elements.

In exemple, in pseudo code :

data = { 0, 10, 42, 5, 3 };
max = 42;  // you already calculated this, so in my example, I hardcode it.
index = 2; // same than above
data[index] = 0;

amountToDistribute = max / (data.length - 1); // 42 / 4 = 10.5, but it's floored to 10 since the division is made on integers
remaining = max % (data.length - 1); // 2 remaining

loop for i = 0 to i < data.length
{
    if (i != index) // don't add to the max index
    {
        data[i] += amountToDistribute; //adding 10
    }
}
// now let's add the 2 remaining
j = index + 1;
while (remaining-- > 0)
{
    if (j >= data.length)
    {
        j = 0; //reset the iterator to 0 if the end was reached
    }
    data[j++]++; // add 1 to data[3] on first iteration, then to data[4] on the second one. It increases j too once added
}
print(data); // { 10, 20, 0, 16, 14 }

In my example, you have 42 to redistribute to the 4 other elements.

You can't redistribute 10.5 to each (I guess you have to use integer only)

Then you'll redistribute at least 10 (10.5 floored is 10, since the division is made on integers) to each elements.

Doing 42 modulo 4, written 42 % 4 gives you the rest of the division 42 / 4, which is 2. The 2 remaining are redistribued the same way you wrote your first algorithm.

This can be tweaked so everything will be done in 1 loop. But it actually does 7 iterations (5 in the first loop, then 2 in the second one) instead of 42.

In that example, if you replace { 0, 10, 42, 5, 3 } by { 0, 10, 4000000000 (4 billions), 5, 3 } it will produce the same (adding 1 billion to each elements, but the max one) in 5 iteration instead of the 4 billions in your algorithm

Upvotes: 1

Related Questions