Being Code Expert

Apple Division

There are $n$ apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.

Example:

Input:  n = 5, arr = {3, 2, 7, 4, 1}
Output: 1

Approach

Java

public class AppleDivision {
    public static void main(String[] args) {

        long n = 5;

        long arr[] = { 3, 2, 7, 4, 1 };
        long sum = 0;

        for (long i = 0; i < n; i++)
            sum += arr[(int) i];
        System.out.println(appleDivision(arr, n, 0, sum));

    }

    static long appleDivision(long arr[], long i, 
      long sumcal, long sum) {
        if (i == 0)
            return Math.abs((sum - sumcal) - sumcal);
        return Math.min(appleDivision(arr, i - 1,
        sumcal + arr[(int) (i - 1)], sum),
                appleDivision(arr, i - 1, sumcal, sum));
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

long long appleDivision(long long arr[], long long i,
                        long long sumcal, long long sum)
{
    if (i == 0)
        return abs((sum - sumcal) - sumcal);
    return min(appleDivision(arr, i - 1, 
      sumcal + arr[i - 1], sum),
               appleDivision(arr, i - 1, sumcal, sum));
}
int main()
{
    long long n = 5;

    long long arr[n] = {3, 2, 7, 4, 1};
    long long sum = 0;

    for (long long  i = 0; i < n; i++)
        sum += arr[i];
    cout << appleDivision(arr, n, 0, sum) << "\n";
    return 0;
}

Creating Strings

Given a string, your task is to generate all different strings that can be created using its characters.

Example:

Input:  s = "aabac"

Output:

20
aaabc
aaacb
aabac
aabca
aacab
aacba
abaac
abaca
abcaa
acaab
acaba
acbaa
baaac
baaca
bacaa
bcaaa
caaab
caaba
cabaa
cbaaa

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

void creatingStrings(string s)
{

    sort(s.begin(), s.end());
    set<string> st;
    do
    {
        st.insert(s);
    } while (next_permutation(s.begin(), s.end()));
    cout << st.size() << "\n";
    for (auto it = st.begin(); it != st.end(); it++)
        cout << *it << "\n";
}
int main()
{
    string s = "aabac";

    creatingStrings(s);

    return 0;
}

Palindrome Reorder

Given a string, your task is to reorder its letters in such a way that it becomes a palindrome (i.e., it reads the same forwards and backward).

Example:

Input:  s = "AAAACACBA"
Output: AAACBCAAA

Approach

Java

public class PalindromeReorder {
    public static void main(String[] args) {
        String s = "AAAACACBA";

        palindromeReorder(s);

    }

    static void palindromeReorder(String s) {

        int f[] = new int[26];
        for (int i = 0; i < s.length(); i++)
            f[s.charAt(i) - 'A']++;

        int cnt = 0;
        for (int i = 0; i < 26; i++) {
            if (f[i] % 2 == 1)
                cnt++;
        }
        if (cnt > 1)
            System.out.println("NO SOLUTION");
        else {

            char[] res = new char[s.length()];
            int m = 0;
            int flag = 0;
            int l = 0, k = s.length() - 1;
            for (int i = 0; i < 26; i++) {
                if (f[i] % 2 == 0) {
                    int x = f[i] / 2;
                    int x1 = f[i] / 2;
                    while (x > 0) {
                        res[l++] = (char) (i + 'A');
                        x--;
                    }

                    while (x1 > 0) {
                        res[k--] = (char) (i + 'A');
                        x1--;
                    }
                } else {
                    flag = 1;
                    m = i;
                }
            }
            if (flag == 0)
                System.out.println(res);
            else {
                for (int j = l;; j++) {
                    res[j] = (char) (m + 'A');
                    f[m]--;
                    if (f[m] == 0)
                        break;
                }
                System.out.println(res);
            }
        }
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

void palindromeReorder(string s)
{

    int f[26] = {0};
    for (int i = 0; i < s.size(); i++)
        f[s[i] - 'A']++;
    string res;
    int cnt = 0;
    for (int i = 0; i < 26; i++)
    {
        if (f[i] & 1)
            cnt++;
    }
    if (cnt > 1)
        cout << "NO SOLUTION\n";
    else
    {

        res.resize(s.size());
        int m = 0;
        int flag = 0;
        int l = 0, k = s.size() - 1;
        for (int i = 0; i < 26; i++)
        {
            if (f[i] % 2 == 0)
            {
                int x = f[i] / 2;
                int x1 = f[i] / 2;
                while (x--)
                    res[l++] = i + 'A';
                while (x1--)
                    res[k--] = i + 'A';
            }
            else
            {
                flag = 1;
                m = i;
            }
        }
        if (flag == 0)
            cout << res << "\n";
        else
        {
            for (int j = l;; j++)
            {
                res[j] = m + 'A';
                f[m]--;
                if (f[m] == 0)
                    break;
            }
            cout << res << "\n";
        }
    }
}
int main()
{
    string s = "AAAACACBA";

    palindromeReorder(s);

    return 0;
}

Arrays sort in ascending and descending order

Example:

Input:   arr = { 1, 4, 6, 7, 3, 2, 8 };
Output: [8, 7, 6, 4, 3, 2, 1]

Approach: Array sort in descending order

Java


import java.util.Arrays;

public class ArraySortAscDesc {
    public static void main(String[] args) {
        int[] arr = { 1, 4, 6, 7, 3, 2, 8 };
        arr = selectionSorting(arr, arr.length);
        System.out.println(Arrays.toString(arr));
    }

    static int[] selectionSorting(int[] arr, int N) {
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++) {
                if (arr[min] < arr[j]) {
                    min = j;
                }
            }
            // Swapping element
            int tmp = arr[min];
            arr[min] = arr[i];
            arr[i] = tmp;
        }
        return arr;

    }
}

Approach: Array sort in ascending order

Java


import java.util.Arrays;

public class ArraySortAscDesc {
    public static void main(String[] args) {
        int[] arr = { 1, 4, 6, 7, 3, 2, 8 };
        arr = selectionSorting(arr, arr.length);
        System.out.println(Arrays.toString(arr));
    }

    static int[] selectionSorting(int[] arr, int N) {
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            // Swapping element
            int tmp = arr[min];
            arr[min] = arr[i];
            arr[i] = tmp;
        }
        return arr;

    }
}

Approach: Array sort in ascending order using inbuild method

Java


import java.util.Arrays;

public class ArraySortAscDesc {
    public static void main(String[] args) {
        int[] arr = { 1, 4, 6, 7, 3, 2, 8 };
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
}

Approach: Array sort from position to position

Java


import java.util.Arrays;

public class ArraySortAscDesc {
    public static void main(String[] args) {
        int[] arr = { 1, 4, 6, 7, 3, 2, 8 };
        Arrays.sort(arr,2,5);
        System.out.println(Arrays.toString(arr));
    }
    
}

// [1, 4, 3, 6, 7, 2, 8]

Approach: Object Array sort in descending order

Java


import java.util.Arrays;

public class ArraySortAscDesc {
    public static void main(String[] args) {
        Integer[] arr = { 1, 4, 6, 7, 3, 2, 8 };
        Arrays.sort(arr, Collections.reverseOrder());
        System.out.println(Arrays.toString(arr));
    }
    
}

Home

Apple Division

Creating Strings

Palindrome Reorder

Arrays sort in ascending and descending order