Slice Down problem in Java (Hacker Rank Interview Questions)

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 elements)
1 4 8       (Subtracted 1 from each elements)
3 7          (Subtracted 1 from each elements)
4             (Subtracted 3 from each elements)

For the above problem, naive approach is to find the minimum in each iteration, subtracting it and copy it in new memory.

There are 2 place where you can improve on memory as well as the time complexity (less iteration).

1. Identify minimum value while subtracting the minimum value

2. Do not copy element to another array, just simple store the last index value and decrease it in 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:

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

HackerRankProjectStructure

Code is as below:

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:

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:
GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

Leave a Reply

Your email address will not be published. Required fields are marked *