HackerRank Stone Division Revisited problem solution

31 July 2024 YASH PAL

In this HackerRank Stone Division, Revisited problem solution we have given Q queries where each query consists of N pile of stones and a set of M distinct integers S. we need to calculate the maximum possible number of moves we can perform and print it on a new line.

HackerRank Stone Division Revisited problem solution

Problem solution in Python.

def solve(n,nums,dp):
    res=0
    for i,v in enumerate(nums):
        if n%v==0 and n>v:
            res=max(res,1+dp[i]*(n//v))
    return res

q=int(input())
for _ in range(q):
    n,m=list(map(int,input().split(" ")))
    nums=list(map(int,input().split(" ")))
    nums.sort()
    dp=[0]*len(nums)
    for i in range(1,len(nums)):
        for j in range(i):
            if nums[i]%nums[j]==0:
                dp[i]=max(dp[i],1+(nums[i]//nums[j])*dp[j])
    print(solve(n,nums,dp))

Problem solution in C++.

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<assert.h>

using namespace std;

long long n,s[1001],s1[1001],ans,dp[1001];
int m,br;
const long long maxi=1e12;
void ocisti()
{
   br=0;
   for (int i=0;i<1001;i++)
    dp[i]=0;
}

void solve()
{
    ocisti();
    scanf("%lld%d",&n,&m);

    assert(1L<=n && 1<=maxi);
    assert(1<=m && m<=1000);

    for (int i=0;i<m;i++)
    {
      scanf("%lld",&s[i]);
      assert(1L<=s[i] && s[i]<=maxi);
      if (s[i]<n && n%s[i]==0)
      {
          br++;
          s1[br-1]=s[i];
      }
    }
    br++;
      s1[br-1]=n;

      sort(s1,s1+br);

   for (int i=0;i<br;i++)
    for (int j=i-1;j>=0;j--)
     if (s1[i]%s1[j]==0)
            dp[i]=max(dp[i],(s1[i]/s1[j])*dp[j]+1);


   printf("%lldn",dp[br-1]);

   return;
}

int main()
{
    int t;
    scanf("%d",&t);
    assert(0<t && t<=10);

  while (t--)
   solve();

 return 0;
}

algorithm, coding problems