Equal Stacks Hackerrank problem solution

                            Dynamic Array Hackerrank

Equal Stacks Hackerrank

You have three stacks of cylinders where each cylinder has the same diameter, but they may vary in height. You can change the height of a stack by removing and discarding its topmost cylinder any number of times.

Find the maximum possible height of the stacks such that all of the stacks are exactly the same height. This means you must remove zero or more cylinders from the top of zero or more of the three stacks until they’re all the same height, then print the height. The removals must be performed in such a way as to maximize the height.

Note: An empty stack is still a stack.

Input Format

The first line contains three space-separated integers, n1, n2, and n3, describing the respective number of cylinders in stacks 1, 2, and 3. The subsequent lines describe the respective heights of each cylinder in a stack from top to bottom:

The second line contains n1 space-separated integers describing the cylinder heights in stack 1.
The third line contains n2 space-separated integers describing the cylinder heights in stack 2.
The fourth line contains n3 space-separated integers describing the cylinder heights in stack 3.
Constraints

0<=n1, n2,n3<=105
0<= height of any cylinder <=100


Output Format

Print a single integer denoting the maximum height at which all stacks will be of equal height.

Sample Input

5 3 4
3 2 1 1 1
4 3 2
1 1 4 1

Sample Output

5

Explanation

Initially, the stacks look like this:

Equal Stacks Hackerrank
Observe that the three stacks are not all the same height. To make all stacks of equal height, we remove the first cylinder from stacks 1 and 2 and then remove the top two cylinders from stack 3 (shown below).

Hackerrank coderinme stack

As a result, the stacks undergo the following change in height:

1. 8-3=5
2. 9-4=5
3. 7-1-1=5
All three stacks now have height=5. Thus, we print 5 as our answer.

Solution

Start by calculating the initial height of each stack, marking the numbers of the topmost cylinders.
If all three heights are equal, then you have your answer (i.e., the current height is the maximal height).
If the heights are not equal, then remove the top cylinder from whichever stack is tallest.
Now that one of the heights has changed, repeat the above steps until you have an answer.

For More Learning visit: https://coderinme.com/

So let’s see the solution in C++ 

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int main() {
int a,b,c,i;
cin>>a>>b>>c;
int d[a],e[b],f[c];
long long int x=0,y=0,z=0;
for(i=0;i<a;i++)
    {       cin>>d[i];
    x=x+d[i];   }

for(i=0;i<b;i++)
   { cin>>e[i];
    y=y+e[i]; }
for(i=0;i<c;i++)
    { cin>>f[i];
    z=z+f[i]; }
int p=0,q=0,r=0; 
     while(x!=y ||y!=z ||x!=z) 
    {
	if(x>y && x>z|| x==y && x>z || x==z &&x>y)
      x=x-d[p++];
     else if(y>x && y>z|| y==x && y>z || y==z &&y>x)
            y=y-e[q++];
     else if(z>x &&z>y || z==y && z>x || z==x &&z>y)
            z=z-f[r++];
  } 
        cout<<x;
   return 0;
}

here you can see in C++ code, first, we take input as a,b,c and then we stored all the cylinder value in for 1st stack in the first array and simultaneously in 2nd and 3rd array also, we are storing sum of each stack value and saving it into x,y & z.

Now let’s come to logic, it’s working on the same function make it equal(make x=y=z), if it’s not,   then remove the top cylinder from largest.

Python Solution

n1, n2, n3 = map(int, raw_input().split())
H1 = map(int, raw_input().split())[::-1]
H2 = map(int, raw_input().split())[::-1]
H3 = map(int, raw_input().split())[::-1]

sum_h1 = sum(H1)
sum_h2 = sum(H2)
sum_h3 = sum(H3)

while not (sum_h1 == sum_h2 and sum_h2 == sum_h3):
    if sum_h1 > sum_h2 or sum_h1 > sum_h3:
        t = H1.pop()
        sum_h1 -= t
    if sum_h2 > sum_h1 or sum_h2 > sum_h3:
        t = H2.pop()
        sum_h2 -= t
    if sum_h3 > sum_h1 or sum_h3 > sum_h2:
        t = H3.pop()
        sum_h3 -= t
print sum_h1

IInd Logic for this problem

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


#define N 100000+10

int a[N];
int b[N];
int c[N];

int main() {
    
    int n1,n2,n3;
    
    cin>>n1>>n2>>n3;
    for(int i = 1; i <= n1; i++)cin>>a[i];
    for(int i = 1; i <= n2; i++)cin>>b[i];
    for(int i = 1; i <= n3; i++)cin>>c[i];

    reverse(a + 1, a + n1 + 1);
    reverse(b + 1, b + n2 + 1);
    reverse(c + 1, c + n3 + 1);

    for(int i = 1; i <= n1; i++) a[i] += a[i - 1];
    for(int i = 1; i <= n2; i++) b[i] += b[i - 1];
    for(int i = 1; i <= n3; i++) c[i] += c[i - 1];

    while(a[n1] != b[n2] || a[n1] != c[n3]) {
        if(a[n1] > b[n2]) n1--;
        if(a[n1] > c[n3]) n1--;
        if(b[n2] > c[n3]) n2--;
        if(a[n1] < b[n2]) n2--;
        if(a[n1] < c[n3]) n3--;
        if(b[n2] < c[n3]) n3--;
    }
    cout << a[n1] << endl;
    return 0;
}
/*
 * Code Author: Akshay Miterani
 * DA-IICT
 */
import java.io.*;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;

public class Main {

	static double eps=(double)1e-7;
	static long mod=(int)1e9+7;
	public static void main(String args[]){
		InputReader in = new InputReader(System.in);
		OutputStream outputStream = System.out;
		PrintWriter out = new PrintWriter(outputStream);
		//---------------My Code-----------------
		int n1=in.nextInt();
		int n2=in.nextInt();
		int n3=in.nextInt();
		long s1=0,s2=0,s3=0;
		Queue<Integer> st1=new LinkedList<Integer>();
		Queue<Integer> st2=new LinkedList<Integer>();
		Queue<Integer> st3=new LinkedList<Integer>();
		
		for(int i=0;i<n1;i++){
			int x=in.nextInt();
			st1.add(x);
			s1+=x;
		}
		for(int i=0;i<n2;i++){
			int x=in.nextInt();
			st2.add(x);
			s2+=x;
		}
		for(int i=0;i<n3;i++){
			int x=in.nextInt();
			st3.add(x);
			s3+=x;
		}
		while(!(s1==s2 && s2==s3)){
			long max=Math.max(s1, Math.max(s2, s3));
			if(s1==max){
				s1-=st1.poll();
			}
			else if(s2==max){
				s2-=st2.poll();
			}
			else{
				s3-=st3.poll();
			}
		}
		out.println(s1);
		out.close();
		//---------------The End------------------

	}

	static class Pair implements Comparable<Pair> {
		long u;
		int v;
		int index=-1;
		public Pair(long u, int v) {
			this.u = u;
			this.v = v;
		}

		public int hashCode() {
			int hu = (int) (u ^ (u >>> 32));
			int hv = (int) (v ^ (v >>> 32));
			return 31 * hu + hv;
		}

		public boolean equals(Object o) {
			Pair other = (Pair) o;
			return u == other.u && v == other.v;
		}

		public int compareTo(Pair other) {
			return Long.compare(u, other.u) != 0 ? Long.compare(u, other.u) : Long.compare(v, other.v);
		}

		public String toString() {
			return "[u=" + u + ", v=" + v + "]";
		}
	}
	public static void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}
	static long modulo(long a,long b,long c) {
		long x=1;
		long y=a;
		while(b > 0){
			if(b%2 == 1){
				x=(x*y)%c;
			}
			y = (y*y)%c; // squaring the base
			b /= 2;
		}
		return  x%c;
	}
	static long gcd(long x, long y)
	{
		if(x==0)
			return y;
		if(y==0)
			return x;
		long r=0, a, b;
		a = (x > y) ? x : y; // a is greater number
		b = (x < y) ? x : y; // b is smaller number
		r = b;
		while(a % b != 0)
		{
			r = a % b;
			a = b;
			b = r;
		}
		return r;
	}
	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream inputstream) {
			reader = new BufferedReader(new InputStreamReader(inputstream));
			tokenizer = null;
		}

		public String nextLine(){
			String fullLine=null;
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					fullLine=reader.readLine();
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
				return fullLine;
			}
			return fullLine;
		}
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

New logic

Step I. got 3 arrays and reverse them, create a new array out of an existing array with each element ‘i’ the sum of all the previous elements. eg: [3,2,1,1,1] -> [1,1,1,2,3] -> [1,2,3,5,8]
So the 3 new array formed would be [1,2,3,5,8] [2,5,9] [1,5,6,7]
Step II. now we can Again reverse the array [8,5,3,2,1] [9,5,2] [7,6,5,1]
Step III. just Take the smallest array i.e. [9,5,2] and traverse the smallest array now you can search element in the other 2 array – if the element is existing in other 2 arrays, STOP there and return the number.

check it if you can as an example Here I start with elem – 9: Which is not existing in other 2 arrays. Next, I start with elem – 5: it is existing in other 2 arrays.

Wolla I got it 5….!!!

……………………………………………Now your problem is solved………………………………………………

All rights reserved. No part of this Post may be copied, distributed, or transmitted in any form or by any means, without the prior written permission of the website admin, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law. For permission requests, write to the owner, addressed “Attention: Permissions Coordinator,” to the admin@coderinme.com

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.