Karthik Vvs
BAN USERThis can be done in O(n/2) i.e O(n) time.
My Algo is as follows:
1) Lets say the 0th element is 'a'
2) 1st element can have 'a+1' or 'a1'
3) 2nd element can have '(a+1)+1','(a+1)1','(a1)+1','(a1)1'. So 'a+2','a','a2'
4) Likewise nth element can have 'an','an2'..'a+n2',a+n'.
5) Now lets say the element we want to search is 'x'. So the difference between 'x' and 'a' will be 'xa'
6) As the difference is 'xa', x should be in a position where it can fall under the series containing 'a+(xa)'.
7) 'a+(xa)' starts from 'xa'th position.
8) Also note that elements will be even/odd alternatively based on the series above.
9) So we will do a linear search from 'xa'th position and increment the index by 2.
int findElement(int[] arr,int x){
int n=arr.length;
int a=arr[0];
for (int i = Math.abs(xa); i < n; i+=2) {
if(arr[i]==x)return i;
}
return 1;
}

Karthik Vvs
July 01, 2015 @thelineofcode your thinking is wrong. at 6:00 its is 180 deg but at 6:55, its not 150 deg as the MINUTES hand is less by 5 min(its not HOUR's hand). And you will also have an offset there as the hour's hand wont be pointing at 7 exactly..it will be very close to 7 but not 7. Please watch your clock more carefully
 Karthik Vvs December 13, 2013No..if the stream ends,my answer is O(1) because, we would have got the answer already before stream ends..and no need to modify it as more characters are not there
 Karthik Vvs November 19, 2013This is very simple!
1. Take a boolean[] ascii=new boolean[256];
2. For each character in stream,make ascii[ascii value of that character]=true;
3. if a new character comes, if(ascii[ascii value of that character]==false) return that character;
else {
ascii[ascii value of that character]=true;
go to next character;
}
Note: We don't have to store the characters coming in the stream..its just sufficient to check which character is 1st non repeating character
Time Complexity: O(n)
Space Complexity: O(1)
This can be done in a better mathematical way like this:
Input:
1.We are given a Point
2.We are given a triangle with 3 points
First compute the equations of the 3 lines using 2 point formula i.e if two points (x1,y1), (x2,y2) are there,the equation of line passing through them is (xx1)/(x2x1)=(yy1)/(y2y1)
a.Now we have 3 equations..take any of those 3 equations and let f(x,y)=ax+by+c be that equation(for simplicity..u can substitute the values of a,b,c here).
To find the point (x4,y4) lies on the triangle or not,if u find f(x4,y4)=0 for any equation,that point lies on triangle..otherwise not.
If the point doesn't lie on triangle,then:
To know whether the point lies inside or outside the triangle:
1.The point should lie to the left of one line of triangle and to the right of another line of that triangle.To get this:
b.Now take origin i.e (0,0) and substitute and calculate f(x,y)..so now f(0,0)=0*x+0*y+c=c(c can be +ve or ve) .If c is +ve,it means origin is right side of that line and if its ve ,it means origin is left side of that line
c.Now calculate f(x4,y4) where (x4,y4) is the given point .if sign(f(x4,y4))==sign(c)..then they both are on the same side of the line..so if f(x4,y4) and c are both +ve..tehy are on right..if both ve,they are on left,if c +ve and f(x4,y4) ve,the point is on the left...
d.if u find the point is left/right of this line,then do this for other 2 lines also
e.if u find the same point is on right/left(respectively) of another line..then its inside the Triangle otherwise its outside the triangle
Thank you avenger ...this is my highest rated answer in Careercup . Thanks for the upvote :)
 Karthik Vvs June 27, 2013no..there is no point of missing number in this question..bcoz there will always be n elements from 1..n and an extra number in the range 1..n..so no missing number cases here..
 Karthik Vvs May 13, 2013this question assumes that u have all the numbers from 1..n and a repeated number which makes the no.of elements n+1..so ur example is wrong...u might take 1,2,3,3,5,4..(one number is added at end to make no.of elements n+1)..then my algorithm works :)
 Karthik Vvs May 13, 2013no..this solution works for duplicate number also..lets say we have numbers 2,3,4,1,4,5 with 4 duplicated and the range is from 1..5 .so after xoring all these numbers with 1..5 we get xor=(2^3^4^1^4^5)^(1^2^3^4^5)=4 which is required :)
 Karthik Vvs May 08, 2013The best possible answer is this:
As 1..n numbers are there in which one number is repeated, XOR all the numbers with 1..n which cancels out all the numbers from 1..n and gives the repeated number
public int repeated(int[] arr,int n){
int xor=0;
for(int i=0;i<arr.length;i++){
xor^=arr[i];
}
for(int i=1;i<=n;i++){
xor^=i;
}
return xor;
}
}
Time Complexity: O(n)
 Karthik Vvs May 07, 2013public static int[] populateArray(int[] arr,int n){
int sum=0;
for(int i=1;i<=n;i++){
sum+=i*i;
arr[i1]=sum;
}
return arr;
}
if this is just finding number of ways,then here is the answer :
1.This is equivalent to x1+x2+x3+...+xn=S where 1<=x1,x2,x3,..xn<=A where x1,x2,..xn are variables whose values are specified on each dice respectively
2.so now let t1=x11,t2=x21,t3=x31,...so now we have (x11)+(x21)+..+(xn1)=S(1+1+..1)=Sn
3.so now we have t1+t2+t3+..+tn=Sn where 0<=t1,t2,..tn<=A1
4.The number of ways of forming x1+x2+..xr=n where x1,is (n+r1)C(r1)(there is a proof :))
5.so now the number of ways = (Sn+n1)C(n1)=(S1)C(n1) (where nCr=n!/(nr)!(r!) )
public static int multiple64(int n){
int mask=1<<31,pos=0;
int i=0;
for(i=0;i<32;i++){
if(mask&n>0)break;
}
pos=32i;
return (pos>6)?1<<(pos+1):64;
}

Karthik Vvs
April 23, 2013 import java.lang.Math;
public static boolean compute(int A,int n){
int x=0,y=0,count=0;
for(x=0;x<pow(A,1/3);x++){
for(y=0;y<pow(A,1/3),y++){
if(pow(x,3)+pow(y,3)==A)count++;
}
}
return (count==n)?true:false;
}

Karthik Vvs
April 23, 2013 import java.lang.Math;
public static boolean compute(int A,int n){
int x=0,y=0,count=0;
for(x=0;x<pow(A,1/3);x++){
for(y=0;y<pow(A,1/3),y++){
if(pow(x,3)+pow(y,3)==A)count++;
}
}
return (count==n)?true:false;
}

Karthik Vvs
April 23, 2013 import java.lang.Math;
public static boolean compute(int A,int n){
int x=0,y=0,count=0;
for(x=0;x<pow(A,1/3);x++){
for(y=0;y<pow(A,1/3),y++){
if(pow(x,3)+pow(y,3)==A)count++;
}
}
return (count==n)?true:false;
}

Karthik Vvs
April 23, 2013 import java.lang.Math;
public static boolean compute(int A,int n){
int x=0,y=0,count=0;
for(x=0;x<pow(A,1/3);x++){
for(y=0;y<pow(A,1/3),y++){
if(pow(x,3)+pow(y,3)==A)count++;
}
}
return (count==n)?true:false;
}

Karthik Vvs
April 23, 2013 import java.lang.Math;
public static boolean compute(int A,int n){
int x=0,y=0,count=0;
for(x=0;x<pow(A,1/3);x++){
for(y=0;y<pow(A,1/3),y++){
if(pow(x,3)+pow(y,3)==A)count++;
}
}
return (count==n)?true:false;
}

Karthik Vvs
April 23, 2013 import java.lang.Math;
public static boolean compute(int A,int n){
int x=0,y=0,count=0;
for(x=0;x<pow(A,1/3);x++){
for(y=0;y<pow(A,1/3),y++){
if(pow(x,3)+pow(y,3)==A)count++;
}
}
return (count==n)?true:false;
}

Karthik Vvs
April 23, 2013 import java.lang.Math;
public static boolean compute(int A,int n){
int x=0,y=0,count=0;
for(x=0;x<pow(A,1/3);x++){
for(y=0;y<pow(A,1/3),y++){
if(pow(x,3)+pow(y,3)==A)count++;
}
}
return (count==n)?true:false;
}

Karthik Vvs
April 23, 2013 This can be done using the method as follows:
1.take an array of sqrt(n)(assuming n is the total # of elements): int[] arr=new arr[sqrt(n)]
2.initially fill it with all the elements of array with the last element of each row
i.e for each x in arr do x=last element of each row in matrix
3.now take int largest=findLargest(arr) where findLargest(arr) computes largest element in the array(this can be done using a max heap and takes O(log(sqrt(N))) and replace the largest element in that array with its previous element in the matrix(i.e if its a[i][j] ,replace it with a[i][j1])
4.now repeat step 3 "k" times..which gives the Kth Largest element
Time Complexity: O(k*log(sqrt(n)))
iteration or recursion can be used as long as the time complexity of the problem doesn't change..its also not hard to implement recursion ...
 Karthik Vvs January 31, 2013public static void joinLL(LL ll1,LL ll2){
joinLL(ll1.first,ll2.first);
}
public static void joinLL(Node first1,Node first2){
if(first1==null  first2==null)return;
Node temp1=first1.next;
Node temp2=first2.next;
first1.next=first2;
if(temp1!=null)first2.next=temp1;
joinLL(temp1,temp2);
}

Karthik Vvs
January 31, 2013 As the question is to find the maximum value..
1.if the vertex value is either 0 or 1 use '+'
2.else use '*' operator..
3.for example if the vertices values are in order 0,4,1,3,2,5..then the max result is ((0+4)+1)*3*2*5
code is as follows:
int result=0;
for each vertex in polygon P:
if(vertex.data==0  vertex.data==1)res+=vertex.data; //considering vertex as a node
else res*=vertex.data;
return res;

Karthik Vvs
January 17, 2013 @jaydee can u explain how did u get the number of BSTs formed is (2n)!/n!(n+1)! ?
 Karthik Vvs December 29, 2012@AAA see my answer above :)
 Karthik Vvs December 04, 2012This is a problem of constructing Best Fit line through all the points(so that the line passes through maximum number of points) using Least Squares Method in regression analysis.So that constructed line is the required line through which we can find the slope and yintercept easily :)
 Karthik Vvs November 23, 2012ya and how to calculate probability of a word and output it in programming?
 Karthik Vvs November 17, 2012@eugene.yarovoi but how to ensure that the probability of a random number to be selected is 1/k??
 Karthik Vvs November 17, 2012Do inOrder Traversal of both the BSTs and u'll get 2 sorted arrays (and elements are unique)..so merge these 2 sorted arrays using Merge Sort and there u go :)
 Karthik Vvs November 17, 2012import java.util.Scanner;
/*
* To change this template, choose Tools  Templates
* and open the template in the editor.
*/
/**
*
* @author suryakarthik.v
*/
public class Division {
static int count=1;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int count=1;
System.out.println("give the dividend");
double m=sc.nextDouble();
System.out.println("Give the divisor");
double n=sc.nextDouble();
System.out.println("The quotient is "+quotient(m,n));
System.out.println("The remainder is "+rem(m,n));
;
}
public static int quotient(double m,double n){
double N=n;
if(m<n)return 0;
else if(m==n)return 1;
else{
for (;n<mN; n=n+N) {
count++;
}
}
return count;
}
public static double rem(double m,double n){
return mn*count;
}
}

Karthik Vvs
November 17, 2012 hash table relies on the hash function so that hash function should ensure the uniformity of all the keys into all the hash positions...
 Karthik Vvs November 10, 2012This code doesn't ensure that k "should" be in the middle ..if k is greater than all the other numbers,then both k's will be at last which is not required
 Karthik Vvs November 09, 2012Sort the string with 3 way quicksort and find duplicate if the value of the current one is equal to the previous one and delete the current one
 Karthik Vvs November 06, 2012y/x+x/x(which is ofcourse y/x+1)
 Karthik Vvs October 25, 2012Use a Min Priority Queue of n elements..when the stream of integers are coming in,first store the n elements and after it,if (n+1)th element comes,remove the min element from the priority queue and add this new (n+1)th element..so at last we'll have the first top n elements :)
 Karthik Vvs October 23, 2012Thanks shyam :)
 Karthik Vvs October 23, 2012no..i think the question is to find combinations which equals to one number IN the array..the key=11 above is not valid
 Karthik Vvs October 21, 2012whats wrong in directly returning i instead of copying i to j and returning j?
 Karthik Vvs October 10, 2012it is sufficient to find the Minimum element of the array as its position tells how many times array is rotated...the code is following
public int rotate(int[] arr){
int min=arr[0];
int i;
for(i=0;i<arr.length;i++){
if(arr[i]<min){
min=arr[i];
}
}
return i;
}

Karthik Vvs
October 09, 2012 Open Chat in New Window
To get the next palindrome of a number, the number should be greater than that number and it should be a palindrome. In the below approach,
I. we first make the number palindrome
II.Increment the numbers in the palindrome to make the number bigger than this number.
1) Make the number as a String and ultimately make it to char array for easy manupulations (lets call this char array "ch").
2) Take 2 variables i=0 and j=n1 and start with ch[i] and ch[j] (where n is the length of the char array) and start copying the left half to the right half to make the number palindrome (remember I above.)
3) See if ch[i]>ch[j]. If it is true, then we don't need to increment anything to make the number bigger(remember II above.). Just copying the left half to the right will be sufficient.
4) However, if ch[i]<ch[j], we need to do some increments to the left half of the array. To be strict, we need to increment the left half of the array only when the middle elements of the array satisfy this condition. (because, even if other elements have ch[i]<ch[j] and for middle elements ch[i]>ch[j], just copying the elements to the right half will be sufficient to make the number bigger).
5) Now, there may be some cases when the element is 9 and it has to be incremented for step II. so, it should be made 0 and 1 is to be carried over to its left element. It may also be 9 and again 1 has to be carried to its left element. So we keep track of this using:
}
6) And then increment the numbers at places i and j and return this array in integer form.
Whole code is displayed below:
}
 Karthik Vvs January 10, 2016