Monday 23 December 2013

Break The Integer

Problem:


Given an integer n, break it in smallest non-repeating subsets.

Eg 1: 5
1 1 1 1 1
2 1 1 1
3 1 1
4 1
5

Eg 2: 10
1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
3 1 1 1 1 1 1 1
4 1 1 1 1 1 1
5 1 1 1 1 1
6 1 1 1 1
7 1 1 1
8 1 1
2 2 2 2 2
3 3 3 1
4 4 2
5 5
6 4
7 3
8 2
9 1
10


Time Complexity (for main logic):


n + n + n + n (for 4 loops)
i.e. 4n
i.e. O(n)

O(n) extra space.

Code:



public class SplitTheInteger {

 private int userInput;
 int[] temp;

 void start( int no ) {
  
  userInput = no;
  temp = new int[userInput];
  
  for (int i = 0; i < userInput; i++) {
   temp[i] = 1;
  }
  
  int len = userInput-1;
  
  /**
   * its working for userinput 5
   * 1 1  1  1  1
   * 2 1  1  1 -1
   * 3 1  1 -1 -1
   * 
   * 4 1 -1 -1 -1 //this is taken care by for
                 *  
                 * loop below while loop so to avoid redundancy i have 
   * made 'no-1'
   * 
   * 5
   */
  while (temp[0] != no-1 ) {
   algo();
   temp[0]++;
   temp[len] = -1;
   len--;
   
  }
  
  for (int i = 2; i <= userInput; i++) {
   /**
    * Suppose i = 3
    * UserInput = 10
    * 10/3 = 3
    * so print 3 three times and call done which will select 
    * such a number that will sum up UserInput i.e. 10
    */
   int m = userInput/i;
   int count = 0;
   while ( count != m ) {
    System.out.print( i + " ");
    count++;
   }
   if(i*count != userInput)
    done(count*i);
   System.out.println();
  }
  

  
 }
 
 
 private void algo() {
  // TODO Auto-generated method stub
  int z = temp[0];
  for (int k : temp) {
   if( k != -1)
    System.out.print(k + " ");
  }
  System.out.println();
  
    
 }


 private void done(int i) {
  // TODO Auto-generated method stub
  for (int j = 1; j <= userInput; j++) {
   if(j+i == userInput) {
    System.out.print(  j );
    break;
   }
   
  }
 }


 public static void main(String[] args) {
  // TODO Auto-generated method stub
  new SplitTheInteger().start(10);
  
 }

}


Good Luck! & Happy Coding!!!

No comments:

Post a Comment