Sovle with prime number.How to avoid the overflow?


  • 0
    I

    Hi, guys, I want to solve it with the following idea, but it hits the overflow. Can some one help me to fix it?
    Here is the idea:
    step 1: map 3 colors (0\1\2) to three prime number, say 2\3\5.
    step 2: go through the array and multiply all the element up, for example: A = [0, 1, 2, 1, 2, 1, 0, 2]
    maps to A' = [2,3,5,3,5,3,2,5], then the multiplied number is multiSum = 2*3*5*3*5*3*2*5 = 13500.
    step 3: divide multiSum with 2 repectly untill the multiSum can not divide by 2 and push back it to A, then do this with 3 and5. when multiSum = 13500:

    divide by 2:13500/2 = 67500 --> A[0] = 0; 6750/2= 3375-->A[1] = 0

    then it can not divide by 2.go to 3. do it repectly until multiSum =1.

    Here is the code:

    class Solution {
        public:
            void sortColors(int A[], int n) {
        		int multiSum = 1;
        		int primeNum[3] = {2,3,5};
        		for (int i = 0 ; i<n; ++i){
        			multiSum *= primeNum[A[i]];
        		}
        		int index = 0;
        		for (int j = 0; j<3; ++j){
        			while(multiSum%primeNum[j] == 0){
        				multiSum /= primeNum[j];
        				A[index] = j;
        				++index;
        			}
        		}
            }
        };

  • 2
    M

    There is no way to do this using the primitive data types. Regardless of how many bits you might allocate for the multisum, the longer tests will vastly outrun what you can do. With ints, like you are using now, an array of all 2s (which you represent with 5) will overflow by the 14th number. There are a few ways to reduce the memory usage, such as the fact that since there are guaranteed to be only the 3 numbers, you can leave one of them as 1. Divide out the other two objects and you will have an array with a+b elements set in order, with a+b+c =n. Because of this, you already know what the third count is; it's all the remaining elements.

    However, there is an easier way of solving this. Take the fact that we know the start will be zeros, and the end will be twos, and you can move the elements into their places using a pair of pointers, swapping the other elements into the middle of the array.

    My version constantly puts a 1 in the traversed spot and puts what was there in the right place if it's a 0 or 2. If it's a 0, then it just overwrites the 1 placed earlier, and if it's a two, then it backs up to put the place that would be overwritten in it's place. By the time the traversing pointer reaches the 2's pointer, all the 0s are behind it and all the 2s are in front of it, with the space between the 0's pointer and the 2's pointer being filled with the 1s that were overwritten.

    public void sortColors(int[] A) {
        int i0 = 0;
        int i2 = A.length-1;
        
        for (int i1 = i0; i1 <= i2; i1++){
            int current = A[i1]; //store current value
            A[i1] = 1;  //replace it with a one
            
            if(current == 0){ //if the current value ==0, put it at the end of the 0 section
                A[i0] = current;
                i0++;
            }
            else if(current == 2){ //if it's 2
                int temp = A[i2];
                A[i1] = temp;
                A[i2] = current;   //swap the values
                i1--;        // and repeat the loop on what had been there
                i2--;
            }
        }
    }

  • 0
    P

    First of all, your solution is a 2-pass algorithm. For the first travel, you calculate the multisum. For the second one, rewrite the arry one by one. It is actually a bad way to count the number of 0 1 and 2, so why not count them directly?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.