In this HackerEarth Maximum borders problem solution you are given two arrays a1, a2,..., an and b1,b2,...,bn. In each step, you can set ai = ai - bi if ai >= bi. Determine the minimum number of steps that are required to make all are equal.

Input format

First line: n 
Second line: a1, a2,...an
Third line: b1, b2,..., bn


hackerEarth Number of steps problem solution


HackerEarth Number of steps problem solution.

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

const int maxn = 5e3 + 17;
int n, a[maxn], b[maxn];
int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	for(int i = 0; i < n; i++)
		cin >> b[i];
	for(int x = *min_element(a, a + n); x >= 0; x--){
		bool ok = 1;
		int ans = 0;
		for(int i = 0; i < n && ok; i++){
			ok &= x == a[i] || b[i] > 0 && x % b[i] == a[i] % b[i];
			if(b[i])
				ans += (a[i] - x) / b[i];
		}
		if(ok)
			return cout << ans << '\n', 0;
	}
	cout << "-1\n";
}