Java Challenge - Number Permutation

This community-built FAQ covers the “Number Permutation” code challenge in Java. You can find that challenge here, or pick any challenge you like from our list.

Top Discussions on the Java challenge Number Permutation

There are currently no frequently asked questions or top answers associated with this challenge – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this challenge. Ask a question or post a solution by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this challenge, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!
You can also find further discussion and get answers to your questions over in Language Help.

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head to Language Help and Tips and Resources. If you are wanting feedback or inspiration for a project, check out Projects.

Looking for motivation to keep learning? Join our wider discussions in Community

Learn more about how to use this guide.

Found a bug? Report it online, or post in Bug Reporting

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

I tried a brute force approach instead of recursion.
I generated all possible permutations [for the number and everything less] (including the permutations with zeros) and then I counted only the ones that worked.
To generate the permutations, I used the binary representation of a long integer as a permutation.
It is horribly inefficient: it requires 2 ^ (z + 4) - 1 permutations to be tested, given number z.
Do not use this algorithm; its really bad.

public class NumberPermutation {

  public static boolean checkPermutationBinary(long x, int expectedBinarySum) {
    int maxNumberOf0s = 4;  
        // is one less than the maximum number of numbers in permutation
    int maxConsecutive1s = 9;  // max number we can use in permutation
    //int i = 0; // position in the binary representation
    long b = 1; // used to test if each binary digit is a 1
    boolean previousWas0 = false;
    int numberOf0s = 0;
    int numberOf1s = 0;
    int numberOfConsecutive1s = 0;
    if ((b & x) != b) { // starts with 0
      return false;
    }

    while (b <= x) { 
      if ((b & x) == b) { // have a 1
        numberOf1s++; 
        numberOfConsecutive1s++;
        if (numberOf1s > expectedBinarySum) {
          return false;
        }
        if (numberOfConsecutive1s > maxConsecutive1s) {
          return false;
        }
        previousWas0 = false;
      }
      else { // hava a 0
        numberOf0s++;
        numberOfConsecutive1s = 0;
        if (previousWas0 || (numberOf0s > maxNumberOf0s)) {
          return false;
        }
        previousWas0 = true;
      }
      b = b << 1; // go to next binary digit
      //i += 1;
    }
    /*  // for displaying the permutation
    if (numberOf1s == expectedBinarySum) {
      b = 1;
      int aggregator = 0;
      while(b <= x) {
        if ((b & x) == b) {
          aggregator++;
        }
        else {
          System.out.print(aggregator);
          System.out.print(" ");
          aggregator = 0;
        }
        b = b << 1;
      }
      System.out.println(aggregator);
    }
    */
    return (numberOf1s == expectedBinarySum);
  }

  public static int makeNumber(int z) {
    if (z > 45) {
      return 0;
    }
    long maxToCheck = Math.round(Math.pow(2, z + 4)) - 1;
    int count = 0;
    for (long n = 1; n <= maxToCheck; n++) {
      if (checkPermutationBinary(n, z)) {
        count++;
      }
    }
    return count;
    //return (int)Math.round(Math.pow(2, z - 1)); // only for z < 6
  }

  public static void main(String[] args) {
    System.out.println(makeNumber(6));
  }
}

I did the challenge with a branching recursion (which I did by having recursion in a loop).
I made lots of little helper functions. And one big recursive function.

I actually generated all the relevant permutations as arrays (which wasn’t really necessary) and created a method to display them.
I did some object-oriented stuff: using an object to store information that didn’t change, and to store the ArrayList of all the possible permutations.
(Note that these permutations are actually permutations with repetition, not the classic permutations usually seen in a Probability class).

My code is quite long.

my code
import java.util.Arrays;
import java.util.ArrayList;

public class NumberPermutation {

  public int requiredTotal; // number z
  public ArrayList<int[]> list; // to store the permutations
  public int maxRecursionDepth = 5; // permuation of 5 numbers at most.

  public NumberPermutation() {
    this.requiredTotal = 0;
    this.list = new ArrayList<int[]>();
  }
  public NumberPermutation(int total) {
    this.requiredTotal = total;
    this.list = new ArrayList<int[]>();
  }
  public NumberPermutation(int total, ArrayList<int[]> listOfArrays) {
    this.requiredTotal = total;
    this.list = listOfArrays;
  }
  public NumberPermutation(int total, int initialCapacity) {
    this.requiredTotal = total;
    this.list = new ArrayList<int[]>(initialCapacity);
  }

  public void print() { // to display the permutations
    for (int[] permutation : this.list) {
      for (int x: permutation) {
        System.out.print(x);
      }
      System.out.print(" ");
    }
    System.out.println();
  }

  private static int min(int a, int b) { return (a < b) ? a : b; }
  private static int max(int a, int b) { return (a > b) ? a : b; }
  
  private static int sum(int[] array) {
    if (array == null) {
      return 0;
    }
    int length = array.length;
    int total = 0;
    for (int i = 0; i < length; i++) {
      total += array[i];
    }
    return total;
  }

  public static int[] combine(int[] array, int end) {
    // makes new array by appending an integer at the end
    if (array == null) {
      return new int[]{end};
    }
    int length = array.length;
    int[] combined = new int[length + 1];
    for (int i = 0; i < length; i++) {
      combined[i] = array[i];
    }
    combined[length] = end;
    //length++;
    return combined;
  }

  public int getPerms(int[] soFar, int minToUse, int maxToUse, int depth) {
    /* soFar is array to store the numbers being considered 
        for the permutation so far
    */
    int totalSoFar = sum(soFar);
    // base cases:
    if (depth > this.maxRecursionDepth) {
      return 0;
    }
    if (totalSoFar > this.requiredTotal) {
      return 0;
    }
    else if (totalSoFar == this.requiredTotal) {
      this.list.add(soFar);
      return 1;
    }
    // recursive case:
    else if (depth < this.maxRecursionDepth) {
      int count = 0;
      // recursion in a loop to do branching recursion: 
      for (int i = minToUse; i <= maxToUse; i++) {
        if ((totalSoFar + i) == this.requiredTotal) {
          this.list.add(combine(soFar, i));
          count += 1;
          break;
        }
        else if ((totalSoFar + i) < this.requiredTotal) {
          int[] combined = combine(soFar, i);
          int newMax = min(this.requiredTotal - totalSoFar, maxToUse);
          // main recursion:
          count += getPerms(combined, minToUse, newMax, depth + 1);
        }
      }
      return count;
    }
    return 0;
  }

  public static int makeNumber(int z) {
    if (z > 45 || z < 1) {
      return 0;
    }
    NumberPermutation nPerm = new NumberPermutation(z);
    /* nPerm.getPerms(soFar, minToUse, maxToUse, depth)
       arguments:
       starting with no permuations yet (so use null).
       put min possible number in permutation as 1, or 9 - (45 - z), 
         whichever is higher.
       max possible number in permutation is 9 or z,
         whichever is lower.
       start with recursion depth 0
    */
    nPerm.getPerms(null, max(1, 9 - (45 - z)), min(9,z), 0);
    //nPerm.print(); // to display the permutations
    return nPerm.list.size();
    // return (int)Math.round(Math.pow(2, z - 1)); // for n < 6 only
  }

  public static void main(String[] args) {
    System.out.println(makeNumber(3));
  }
}