CODEWITHSUNDEEP
javaalgorithm
ketan anand
ketan anand

Reputation: 43

Changing the bits in an array

I have an array of bits. Bits will be toggled off and on according to following criteria: 1. if the bits left and right of bit is on put the bit to one otherwise zero. 2. boundary condition(leftmost and rightmost bit will only depend on one bit. ie either left of it or right of it.

this array will be processed m times with the following criteria.

I wrote the following code where A is the original array and subsiquent is the array for processing. But this will give me O(nm) where n is the length and m is no of times i want to do the process. Please suggest me some alternative for the solution so that i can decrease my complexity. 

for(int k = 0;k < m;k++){
  for(int l = 0;l < n;k++){
    if(l == 0){
      if(A[l+1]==1)
        subsiquent[l]=1;
      else
        subsiquent[l]=0;
      //** is there a } missing here?
      else if(l==n){
        if(A[l-1]==1)
          subsiquent[l]=1;
        else
          subsiquent[l]=0;                        
      } else {
        if(A[l+1]==1 && A[l-1]==1 ){
          subsiquent[l]=1;
        }else{
          subsiquent[l]=0;
        }
      } 
    //** or is there a } missing here?      
  }

  A = subsiquent;
}

Upvotes: 3

Views: 82

Answers (1)

Treziac
Treziac

Reputation: 3264

Some things to see:

  • If your last p first or p last bits are 0, they will always stay 0, and so will bit p+1 (resp. p-1) . So you can add a check on this, and reduce the start / end of your l loop (and change p+1 digit to 0)
  • Similaraly, if p first (resp last) digits are 1, then p-1 digits will stay at 1 andbit p will be 0
  • I you have all zero or all 1, no more changed are needed
  • the same thing can be done in the middle of your array (5 zero in the middle? There will be 7 next time. Five 1? The three middle will stay 1), but not sure it's easy to integrate (only if you have say 1000 same bit is it worth dealing with it I think)
  • If you don't end to all 0 or all 1, you will have an alternate of 0 and 1. So you can also check if ou are alternating 0 and 1, and with a modulo 2 on remaining m, you can predict the result

Edit: with p>=2 in my examples for extremities of course

Edit: you can represent your array as the number of similar bits in an int array + memorizing the first bit 000111101100110101 would be represented as [0]3412221111 (begin with zero, then 3 zero, then 4 one, then 1 zero, then 2 one, etc.)

I didn't check all, but you can infer the rule to go from one step to an other rather easily with minimum step. (there are many cases, I let you find them. You only have to go from left to right and remember that you switch from 0 and 1, but may have to modify/decrease the number on the right when iterating, or inserting number. A linked list will be well suited here)

For example, the steps will be:

000111101100110101  [0]3-4-1-2-2-2-1-1-1-1      
000011010000001010  [0]4-2-1-1-6-1-1-1-1
000000100000000101  [0]6-1-8-1-1-1
000000000000000010  [0]16-1-1
000000000000000001  [0]17-1
000000000000000000  [0]18

Upvotes: 1

Related Questions