Friday, September 13, 2013

divide a gievn array into two set of numbers such that the difference between the sum of those set is minmum ie do balance partioning



 
    public static void doBalanacePartition(int[] arr) {
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        int num = sum / 2;
        int k = num;
        while (!findNumSetBySum(arr, k)) {
            k++;
        }
        int j = num;
        while (!findNumBySum(arr, j)) {
            j--;
        }
    }


static boolean findNumBySum(int[] arr, int sum) {
        System.out.println("find all those two numbers whose sum is a given num : " + sum);
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            if (arr[i] + arr[j] > sum) {
                j--;
            } else if (arr[i] + arr[j] < sum) {
                i++;
            } else {
                System.out.println(arr[i] + " , " + arr[j]);
                i++;
                j--;
            }
        }
        return false;
    }

No comments:

Post a Comment