PROBLEM LINK:Author: Pavel Sheftelevich DIFFICULTY:CAKEWALK PREREQUISITES:Simple math PROBLEM:You have $N$ coins. You are about to call any number of people between $1$ and $K$ and divide the coins to them in such a way that each person gets the same amount of coins and this amount is maximal. You take all coins left after this process. Your task is to compute the maximal number of coins which you can get. QUICK EXPLANATION:For each possible number of people, compute the amount of coins which are left after the process. Finally, return the maximum from these values. EXPLANATION:Let assume that you decided to call exactly $k$ people and you want to divide $N$ coins to them in the way described in the statement. It means, that each person gets the same amount of coins and this amount is maximal from all possible ones. You can simulate this process by giving one coin to all people at once until you have less than k coins, because then you cannot divide them equally. The number of coins which each person has after the process equals $N \mathbin{/} k$, where $\mathbin{/}$ is the integer division, i.e. $7 \mathbin{/} 3 = 2$. Based on this fact, it is easy to see that there are $r = N  k \cdot (N \mathbin{/} k)$ coins left after the process and this is the amount of coins which you get. Here $r$ is called a remainder after dividing $N$ by $k$ and it is very common in computation. Most programming languages have built in operation for computing a reminder. It is often represented by $\texttt{%}$ or $\texttt{mod}$. Since $K$ is not so big, we can iterate over all possible values of it and for each of them, compute the remainder of $N \mathbin{/} k$, where k is the current number of people, and at the end print the maximum from these remainders. Time complexity: We are iterating over K values and for each of them we do constant time operations, so the total complexity is $O(K)$. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here
This question is marked "community wiki".
asked 26 Jul '15, 14:36

can anyone post much optimize method for this problem?? as this problem has very few test cases it works for this only... suppose problems has large test cases...10000 than this solution give tle.. answered 25 Aug '15, 13:44

worst case complexity : K/2 better than editorial solution's time complexity: here is my code
Idea of this solution is simple to analyze this solution you can just take number and see what all value of mod if you are trying divide n with k where n>k then you will definitely get this.. HAPPY CODING answered 25 Aug '15, 14:01

What's wrong with my code? import java.util.Scanner; class GDOG { public static void main(String args[]) { Scanner in=new Scanner(System.in); int t=in.nextInt(); for ( int i=0; i<t; i++="" )="" {="" int="" n="in.nextInt();" int="" k="in.nextInt();" int="" res="nk;" while="" (="" res="">=0 ) { n=res; res=nk; } System.out.println(n); } } } answered 05 Dec '15, 00:23

whats wrong with my code? include <iostream>include <stdio.h>include <algorithm>include <iomanip>include <math.h>include <string.h>using namespace std; int main() { int t,i; cin>>t; for (int z=1; z<=t; z++) {
} answered 12 Dec '15, 19:44

I thought the solution would simply be N%K but that seems to be incorrect. What am I missing? answered 14 May '16, 05:40

Not working why??? import java.util.Scanner; class puppy{ public static void main(String args[]){ Scanner ashok=new Scanner(System.in); int test=ashok.nextInt(); int i; for(i=1;i<=test;i++){ int coins=ashok.nextInt(); int people=ashok.nextInt(); int j=1,x=1,count=1; while(j>0){ count=peoplex; if(count>coins){ System.out.println(coins(people(x1))); break; } //if(count==coins){ //System.out.println("0"); //break; //} x++; } } } } answered 25 May '16, 10:10

/ * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools  Templates * and open the template in the editor. / package javaapplication60; / Author : Pujan / import java.util.Scanner; class stack { public static void main(String[] args) { Scanner in = new Scanner(System.in); int x,y;
answered 25 May '16, 11:52

include<iostream>using namespace std;
int main()
{
int t;
cin>>t;
while(t)
{
int n,k;
cin>>n>>k;
int r=0;
while(k)
{
if((n(n/k)k)>r)
{
r=n(n/k)k;
}
else
break;
k;
}
cout<<r<<endl; answered 26 Jun '16, 20:16

include<iostream>using namespace std; int main() { long t,n,k,ans,i,a; cin>>t; while(t) { cin>>n>>k; ans=0; for(i=2;i<=k;i++) { a=n%i; if(ans<a) ans=a; } cout<<ans<<"\n";
return 0; } answered 11 Mar '17, 17:22

What is wrong with this code? #include <iostream> using namespace std; int main() { int x,y,t; cin>>t; while(t>0){ cin>>x>>y; if(y==0) cout<<x; else cout<<x%y<<endl; t; } return 0; } answered 15 Apr '17, 09:34

What is wrong with this code?
} answered 15 Apr '17, 09:40

Okay after scratching my head for sometime I got what the problem is about. The problem statement is somewhat misleading. The value of k is the number of people around the dog. We have to iterate over k to check how many people he should call so that the remainder is maximum. So simple n%k would not work and you have to find a number between 1 and k for which n%k is maxmimum. answered 25 Mar, 15:46

answered 05 Dec, 15:32

include <iostream>
using namespace std; int main() { long n,k,m,r; int t; cin>>t; while(t) {cin>>n>>k; m=n/k; r=n(m*k); cout<<r<<endl;
}
WHAT WRONG IN MY CODE???