nikunjsoni

927

Jul 17th, 2021
139
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     vector<int> threeEqualParts(vector<int>& A) {
  4.         // Count no of 1's in the given array
  5.         int countNumberOfOnes = 0;
  6.         for(int c: A)
  7.             if(c == 1)                  
  8.                 countNumberOfOnes++;
  9.                                
  10.         // If no 1 is found, that means we can return ans as {0, size-1}
  11.         if(countNumberOfOnes == 0)      
  12.             return {0, A.size()-1};
  13.                        
  14.         // If no of 1's is not a multiple of 3, then we can never find a possible partition since
  15.         // there will be atkeast one partition that will have different no of 1's and hence
  16.         // different binary representation
  17.         // For example,
  18.         // Given :
  19.         // 0000110  110  110
  20.         //       |  |    |
  21.         //       i       j
  22.         // Total no of ones = 6
  23.         // 0000110         110      110
  24.         //     |           |        |
  25.         //     start       mid      end
  26.         // Match starting from first 1, and putting 2 more pointers by skipping k 1's
  27.        
  28.         if(countNumberOfOnes % 3 != 0)            
  29.             return {-1, -1};
  30.                        
  31.         // find size of each partition
  32.         int k = countNumberOfOnes/3;
  33.         int i;
  34.        
  35.         // find the first 1 in the array
  36.         for(i=0;i<A.size(); i++)
  37.             if(A[i] == 1)
  38.                 break;
  39.         int start = i;
  40.        
  41.         // find (k+1)th 1 in the array
  42.         int count1 = 0;
  43.         for(i=0;i<A.size(); i++)
  44.         {
  45.             if(A[i] == 1)
  46.                 count1++;
  47.             if(count1 == k + 1)
  48.                 break;
  49.         }
  50.         int mid = i;
  51.        
  52.         //find (2*k +1)th 1 in the array
  53.         count1= 0;
  54.         for(i=0;i<A.size(); i++)
  55.         {
  56.             if(A[i] == 1)
  57.                 count1++;
  58.             if(count1 == 2*k + 1)
  59.                 break;
  60.         }
  61.         int end = i;
  62.        
  63.         // Match all values till the end of the array
  64.         while(end< A.size() && A[start] == A[mid] && A[mid] == A[end])
  65.         {
  66.             start++; mid++; end++;
  67.         }
  68.        
  69.         // Return appropriate values if all the values have matched till the end
  70.         if(end == A.size())
  71.             return {start-1, mid};
  72.        
  73.         // otherwise, no such indices found
  74.         return {-1, -1};
  75.     }
  76. };
RAW Paste Data