Given array of ints. Assuming total no. of elements is even. Need to tell whether this array can be grouped in sets of pairs such that sum of each pair is divisible by K.
eg: 0,2,4,8,12,20,18,4 and k=4
so (0,8), (2,18), (4,20), (4,12) is one such set in which sum of each pair is divisible by k.
Solution:
class Solution{
static boolean find(int []arr, int k){
if(arr == null || arr.length == 0)
return false;
int len = arr.length;
if(len % 2 != 0)
return false;
int count= 0;
for(int i = 0; i < len; i++){
for(int j = i+1; j < len; j++){
if(arr[j] != -1){
int t = arr[i] + arr[j];
if(t %k == 0){
count++;
arr[j]=-1;
break;
}
}
}
}
return (count == len/2);
}
public static void main(String... args){
int []arr = {0,2,4,8,12,20,18,4};
int k =4;
System.out.println(find(arr,k));
}
}
eg: 0,2,4,8,12,20,18,4 and k=4
so (0,8), (2,18), (4,20), (4,12) is one such set in which sum of each pair is divisible by k.
Solution:
class Solution{
static boolean find(int []arr, int k){
if(arr == null || arr.length == 0)
return false;
int len = arr.length;
if(len % 2 != 0)
return false;
int count= 0;
for(int i = 0; i < len; i++){
for(int j = i+1; j < len; j++){
if(arr[j] != -1){
int t = arr[i] + arr[j];
if(t %k == 0){
count++;
arr[j]=-1;
break;
}
}
}
}
return (count == len/2);
}
public static void main(String... args){
int []arr = {0,2,4,8,12,20,18,4};
int k =4;
System.out.println(find(arr,k));
}
}
import java.util.Hashtable;
ReplyDeletepublic class Sample {
public static void main(String... args){
int []arr = {0,2,4,8,12,20,18,4,6,2,4,5,3,8,1,3,4,7,5, 88};
int k =4;
System.out.println(AreAllPairsDivisible(arr,k));
}
private static boolean AreAllPairsDivisible(int[] arr, int k) {
//Insert into Hashtable, determine the largest number:
Hashtable ht = new Hashtable();
int largest = insertAndReturnLargest(arr, ht);
for(int i: arr){
if(ht.get(i) > 0){ //If the number has not been used already.
int n = 0;
while(true){
int currentTarget = (n*k) - i;
if(currentTarget > largest){
break;
}
if(currentTarget == i){
if(ht.get(i) >= 2){
ht.put(i, ht.get(i) - 2);
break;
}
}
else if(ht.containsKey(currentTarget)){
if(ht.get(currentTarget) > 0){
ht.put(i, ht.get(i) - 1);
ht.put(currentTarget, ht.get(currentTarget) - 1);
break;
}
}
n++;
}
}
}
for(Integer i: ht.keySet()){
if(ht.get(i) > 0)
return false;
}
return true;
}
private static int insertAndReturnLargest(int[] arr,
Hashtable ht) {
int largest = -1;
for(int i: arr){
if(i > largest)
largest = i;
if(ht.containsKey(i)){
int currentValue = ht.get(i);
ht.put(i, currentValue + 1);
}
else {
ht.put(i, 1);
}
}
return largest;
}
}
Time Complexity: O(N)
Please check ideone link (formatted)
ReplyDeletehttp://ideone.com/B8dbNU