Advertisement
bekanaveriani

CanBalance problem

Jul 20th, 2019
168
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.36 KB | None | 0 0
  1.  private  int sumBalance(int[] nums, int startIndex, int endIndex, int lastStartIndex, int lastEndIndex,
  2.                                   int lastCount) {
  3.         int sum = lastCount;
  4.  
  5.         if (startIndex < lastStartIndex) {
  6.             for (; startIndex < lastStartIndex; startIndex++) {
  7.                 sum += nums[startIndex];
  8.             }
  9.         } else if (startIndex > lastStartIndex) {
  10.             for (; startIndex > lastStartIndex; lastStartIndex++) {
  11.                 sum -= nums[lastStartIndex];
  12.             }
  13.         }
  14.  
  15.         if (endIndex > lastEndIndex) {
  16.             for (; lastEndIndex < endIndex; lastEndIndex++) {
  17.                 sum += nums[lastEndIndex];
  18.             }
  19.         } else if (endIndex < lastEndIndex) {
  20.             for (; endIndex < lastEndIndex; endIndex++) {
  21.                 sum -= nums[endIndex];
  22.             }
  23.         }
  24.  
  25.         if (sum == 0) {
  26.             for (; startIndex < endIndex; startIndex++) {
  27.                 sum += nums[startIndex];
  28.             }
  29.         }
  30.  
  31.         return sum;
  32.     }
  33.  
  34.  
  35.     private boolean checkBalance(int[] nums, int leftStart, int leftEnd, int lastLeftStartIndex, int lastLeftEndIndex, int lastLeftCount,
  36.                                  int rightStart, int rightEnd, int lastRightStartIndex, int lastRightEndIndex, int lastRightCount, boolean leftWasMore) {
  37.  
  38.         if (nums.length < 2) return false;
  39.  
  40.  
  41.         int sumLeft = sumBalance(nums, leftStart, leftEnd, lastLeftStartIndex, lastLeftEndIndex, lastLeftCount);
  42.         int sumRight = sumBalance(nums, rightStart, rightEnd, lastRightStartIndex, lastRightEndIndex, lastRightCount);
  43.  
  44.         if (sumLeft < sumRight) {
  45.             if (leftWasMore) return false;
  46.             return checkBalance(nums, leftStart, leftEnd + 1, lastLeftStartIndex, leftEnd, sumLeft,
  47.                     rightStart + 1, rightEnd, rightStart, rightEnd, sumRight, false);
  48.         } else if (sumLeft > sumRight) {
  49.             return checkBalance(nums, leftStart, leftEnd - 1, lastLeftStartIndex, leftEnd, sumLeft,
  50.                     rightStart - 1, rightEnd, rightStart, rightEnd, sumRight, true);
  51.         }
  52.  
  53.         return true;
  54.  
  55.     }
  56.  
  57.     public boolean canBalance(int[] nums) {
  58.         return checkBalance(nums, 0, nums.length/ 2, 0, nums.length/ 2, 0,
  59.                             nums.length/ 2, nums.length, nums.length / 2, nums.length, 0, false);
  60.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement