Power Of Minimum
All submissions for this problem are available.
You are given an array of n integers.
You are asked to choose the minimum number (say x) from the array you have at any instant and delete it. Now, the interesting thing is that along with the number you also need to delete any number in the array such that it satisfies the condition (array[i]%x==0).
*NOTE that you can only delete a particular integer once at each step of your deletion.
Now your task is to perform such a deletion any number of times till the array gets empty and tell the minimum number of steps required to delete the entire array.
The first line of the input contains an integer n denoting the number of integers in the array.The second line contains n space-separated integers A1, A2.......An denoting the contents of the array.
Output contains a single integer denoting the minimum number of steps required
- 1 ≤ n ≤ 100000
- 1 ≤ array[i] ≤ 1000000
Input: 5 3 2 6 5 4 Output: 3
At step1, 2 is picked and 2, 6 and 4 are deleted and the array becomes (3 5)
At step2, 3 is picked and deleted and the array becomes (5)
At step3, 5 is picked and deleted and the array becomes () i.e. empty.
|Tags||easy-medium, mightysg, number-theory|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.