dilip kasana
BAN USEREnter your state here
- 3of 3 votes
AnswersYou are given an array of N elements.arrange array in such a way that sum of any cunsucative k numbers are divisible
- dilip kasana in India
by NUM.if not possible print -1.(it may possible that there are many solution possible then return any one)
For example:
N=6
k=3
NUM=63
array={80,17,90,82,27,19}
Answer:{19,17,27,82,80,90}
any 3 cunsucative no. like (27+82+80)%63=0
another solution={27,19,17,90,82,80}
may be a hint :try to group all no.'s in mod NUM map and use vector and map.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm
I am agree with euqene.yarovi
actually it should be if distinct set of (arr[i]%NUM) >k
then print "-1"
else apply "YOUR ALGO"
I am sure.
I have problem here
arr={2 ,5, 0 ,9 ,1, 9 ,9 ,4}
n=8,k=3, NUM=2,
hash array={0,1,0,1,1,1,1,0}
so if i start from {9,4,9.......} then i got{9,4,9,1,0,9,5,2}
and if start as {4,9,9....} then got {4,9,9,0,9,5,2,1}
these working but if start as {9,9,4.....}then getting no working solution...................Can u explain in this scenario how to???
And also it is not necessary to having k unique elements such as if we have
k=3,NUM=4,N=6
arr={6,1,1,9,2,5}
then hash{2,1,1,1,2,1} there are 2 unique numbers and sulution exists as Ans={1,1,2,5,9,5,6}.
Can you improve it
very very appreciative solution...
I would like to know from u that how you select first three elements as 17,19,27.can u please & please explain an algorithm to select first sequence of k elements. like 17,19,27
It depends on sizeof(int) as well.
you are using sizeof(int)=2
right me if i am wrong
Lets take the Machine as Big Endian (Read from left to right)
and size of int as 4.
size of inner most Union D=max{size of char,size of int[5]} = 20 bytes ======5*sizeof(int)
size of Union C=max{size of int , size of Union D} = 20 bytes
size of Union B= max { size of double , size of Union C} =20 bytes
size of the whole Union=max {size of long int[5],size of Union B}= 5*sizeof(long int) = 20
if we store p->b.a.k= 15 in union
because it is an int so it will take first 4bytes and the whole 20 bytes will look as
000F 0000 0000 0000 0000 in Hexadecimal
So when reading p->b.a.s.x[0] as first int it will print 15
and reading p->y[0] as long int it will again print 15 because both are 4 byte.
If additional space is provided then
import java.util.HashMap;
import java.util.Scanner;
public class IntwoSetsValueEqualsToAplusB {
public static void main(String[] args) {
Integer setA[]={180,84,168,171,195,42,71,164,59,118,102,135,78,110,204,196,136,154,30,130,3,52,29,172,33,86,27,23,214,46,110,180,131,63,136,112,105,208,62,165,113,165,85,191,60,75,173,197,14,203,112,18,41,142,191,74,13,4,98,13,51,208,193,182,57,115,80,163,110,143,114,8,93,200,199,154,61,158,137,76,147,35,94,188,178,70,49,191,75,147,205,126,141,184,94,198,85,174,146,195};
Integer setB[]={84,71,102,89,87,78,6,6,7,8,89,9};
int value=new Scanner(System.in).nextInt();
HashMap<Integer, Integer> hm=new HashMap<Integer,Integer>();
hm=buildmap(setB);
for(int i:setA) if(hm.containsValue(value-i)) System.out.println(i);
}
private static HashMap<Integer, Integer> buildmap(Integer[] setB) {
HashMap<Integer, Integer> hm=new HashMap<Integer,Integer>();
for(Integer i:setB) hm.put(i.hashCode(),i);
return hm;
}
}
in O(n+m)
#include<stdio.h>
int main()
{
int i,output=0,mask=1,min,max;
printf("enter two no.'s);
scanf("%d%d",&min,&max);
if(min>max)
{
i=min;
min=max;
max=i;
}
for(i=1;mask<=min;i++,mask=mask*2,max<<=1) if(min&mask) output+=max;
printf("%d",output);
}
//Complexity= no. of bits in lesser number
can u explain the second
- dilip kasana May 19, 2012can u explain the second
- dilip kasana May 19, 20121.iterate through array as O(n) complexity
2.set flag to 1 if 2 consecutive no's are in increasing and set it to -1 if negative.
3.if there is 0 then skip and keep the location of last no. for consecutive no. say index.
4.compare currentindex-th element with index-th element. if flag changes increase lastindex else set startindex=currentindex
1.iterate through array as O(n) complexity
2.set flag to 1 if 2 consecutive no's are in increasing and set it to -1 if negative.
3.if there is 0 then skip and keep the location of last no. for consecutive no. say index.
4.compare currentindex-th element with index-th element. if flag changes increase lastindex else set startindex=currentindex
wrong working
- dilip kasana May 18, 2012not optimal
- dilip kasana May 16, 2012find out the critical point and apply binary search
- dilip kasana May 13, 2012find out the critical point and then recursively search in both part
- dilip kasana May 13, 2012
print "-1"
- dilip kasana October 26, 2012