Input: array of integer value
Output: print each iteration by subtracting the smallest elements till array becomes empty
For example:
For input array: 4, 3, 5, 8, 12
At each iteration, find minimum number and subtract it from element and print non-zero elements
1 2 5 9 (Subtracted 3 from each element)
1 4 8 (Subtracted 1 from each element)
3 7 (Subtracted 1 from each element)
4 (Subtracted 3 from each element)
For the above problem, a naive approach is to find the minimum in each iteration, subtracting it and copy it in new memory.
There are 2 places where you can improve on memory as well as the time complexity (less iteration).
- Identify minimum value while subtracting the minimum value
-
Do not copy element to another array, just simply store the last index value and decrease it in a recursive call.
Below is the screen shots of my project directory and the code for the above solution:
You can also clone the repository from GIT using the link below:
https://github.com/Niravkumar-Patel/SnippetExampleRepo.git
Code is as below:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
public class SliceDown { public static void main(String args[]){ SliceDown sd = new SliceDown(); int a[] = {15,12,10,5,3}; printArray(a, a.length); int smallestIndex = findSmallest(a); sd.sliceDown(a,a.length,smallestIndex); } /* * recursively call this method by passing the index value of * min number and the range that needs to be sliced down */ public void sliceDown(int a[],int range, int smallestIndex){ int new_range = 0; int new_smallestIndex = -1; int smallNumber = a[smallestIndex]; for(int i=0;i<range;i++){ // To skip the number which is going to be slice down if(a[i]!=smallNumber){ a[new_range] = a[i] - smallNumber; //To initialize & find the new minimum number for next iteration if(new_smallestIndex<0){ new_smallestIndex = new_range; }else if(a[new_range] < a[new_smallestIndex]){ new_smallestIndex = new_range; } new_range++; } } printArray(a,new_range); if(new_range>1){ sliceDown(a, new_range,new_smallestIndex); } } //This method will be called only once for the first iteration private static int findSmallest(int a[]){ int smallestIndex = 0; for(int i=1;i<a.length;i++){ if(a[smallestIndex]>a[i]){ smallestIndex = i; } } return smallestIndex; } public static void printArray(int a[],int range){ for(int i=0;i<range;i++){ System.out.print(a[i]+" "); } System.out.println(""); } } |
The output of the above code:
|
1 2 3 4 5 |
15 12 10 5 3 12 9 7 2 10 7 5 5 2 3 |
Again you can find the above code on git repo:
https://github.com/Niravkumar-Patel/SnippetExampleRepo.git