In this paper, we develop four malware detection methods using Hamming\ndistance to find similarity between samples which are first nearest neighbors\n(FNN), all nearest neighbors (ANN), weighted all nearest neighbors (WANN), and\nk-medoid based nearest neighbors (KMNN). In our proposed methods, we can\ntrigger the alarm if we detect an Android app is malicious. Hence, our\nsolutions help us to avoid the spread of detected malware on a broader scale.\nWe provide a detailed description of the proposed detection methods and related\nalgorithms. We include an extensive analysis to asses the suitability of our\nproposed similarity-based detection methods. In this way, we perform our\nexperiments on three datasets, including benign and malware Android apps like\nDrebin, Contagio, and Genome. Thus, to corroborate the actual effectiveness of\nour classifier, we carry out performance comparisons with some state-of-the-art\nclassification and malware detection algorithms, namely Mixed and Separated\nsolutions, the program dissimilarity measure based on entropy (PDME) and the\nFalDroid algorithms. We test our experiments in a different type of features:\nAPI, intent, and permission features on these three datasets. The results\nconfirm that accuracy rates of proposed algorithms are more than 90% and in\nsome cases (i.e., considering API features) are more than 99%, and are\ncomparable with existing state-of-the-art solutions.\n