HackerEarth Assorted Arrangement problem solution

In this HackerEarth Assorted Arrangement problem solution, You have a set of n distinct positive numbers. You also have m colors. Your colors are labeled from 1 to m. You’re also given a list c with m distinct integers.

You paint the numbers according to the following rules: For each i in order from 1 to m, paint numbers divisible by c[i] with color i. If multiple rules apply to a number, only the last rule applies.

You sorted your set of numbers and painted them. It turns out that no number was left unpainted. Unfortunately, you lost the set of numbers you had originally. Return the smallest possible value of the maximum number in your set. The input will be constructed such that it’s guaranteed there is at least one set of numbers that is consistent with the given information.

HackerEarth Assorted Arrangement problem solution.

import java.util.Scanner;

public class AssortedArrangement {
  public static void main (String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt(), m = in.nextInt();
    int[] c = new int[m];
    for (int i = 0; i < m; i++) c[i] = in.nextInt();
    int[] x = new int[n];
    for (int i = 0; i < n; i++) x[i] = in.nextInt()-1;
    int last = 0;
    for (int i = 0; i < n; i++) {
      last = (last/c[x[i]]+1)*c[x[i]];
      while (true) {
        boolean ok = true;
        for (int j = x[i]+1; j < m; j++) {
          if (last % c[j] == 0) {
            ok = false;
            break;
          }
        }
        if (ok) break;
        last += c[x[i]];
      }
    }
    System.out.println(last);
    System.exit(0);
  }
}

Second solution

#include<bits/stdc++.h>

using namespace std;

const int N = 500031;

int n, m;
int mark[N];
int ans;

bool bad(int val, int ps)
{
    if (val%mark[ps])
        return true;
    for (int i = ps + 1; i <= m; i++)
    {
        if (val%mark[i] == 0)
            return true;
    }
    return false;
}

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        cin >> mark[i];
    }

    ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ++ans;
        int val;
        cin >> val;
        while (bad(ans, val))
            ++ans;
    }

    cout << ans << endl;

    return 0;
}

HackerEarth Assorted Arrangement problem solution

HackerEarth Assorted Arrangement problem solution.

Second solution

Leave a Reply

Pages

Practice