sagartiwari230
BAN USERDistance between 2 node a,b in a tree is given as:
dis(a,b) = dis(root,a) + dis(root,b) - 2*dis(root,lca(a,b));
where
lca(x,y) is Least Common Ancestor of node x and node y
@smile.jain, your approach will not work. Consider the string str = "ABC", XOR of each character is not zero so your function will return false, but for given string ans is true as it contains all unique character.
- sagartiwari230 July 06, 2017As node structure is given so it is either a singly linked list or circular linked list. For simplicity let's assume it is singly linked list. So my idea here is to traverse through the linked list and maintain 2 pointers one indicating start of word (say i) and other indicating end of word (j), I will also use string s which contains character from node i to node j and whenever I encounter the space, I would replace reverse of string to the node i through j.
I think by looking at code, you will get more understanding
import java.util.*;
import java.lang.*;
import java.io.*;
class Solution {
static class Node {
char val;
Node next;
Node(char ch){
this.val = ch;
next = null;
}
}
static Node reverse (Node head) {
Node i=head,j=head;
Node temp = head;
String s = "";
while(temp!=null){
if(temp.val==' '||temp.next==null) {
if(temp.val!=' ')
s = s+temp.val;
int z = s.length()-1;
while(z!=-1){
i.val = s.charAt(z--);
i = i.next;
}
s= "";
i = temp.next;
j = temp.next;
}
else{
s += temp.val;
j = j.next;
}
temp = temp.next;
}
return head;
}
public static void main (String[] args) {
Node temp = null;
Node head = new Node('H');
head.next = new Node('e');
head.next.next = new Node(' ');
head.next.next.next = new Node('W');
head.next.next.next.next = new Node('o');
System.out.println("INPUT:");
temp = head;
while(temp!=null) {
System.out.print(temp.val);
temp = temp.next;
}
System.out.println();
head = reverse(head);
System.out.println("OUTPUT:");
temp = head;
while(temp!=null) {
System.out.print(temp.val);
temp = temp.next;
}
}
}
Space Complexity: At any point in time max length of string s would be size of longest word in given input, so space would be O(|No. of characters in longest word|)
Time Complexity: if there are M words and size of each word is N then time complexity is O(MN)
@funk, solution which I proposed using set would take O(n) space, but I can improve it to O(1) by using sorting.
Basically Idea goes like this,
1. sort the array
2. for each position i upto n-2:
left = position next to i
right = last position i.e. n-1;
while(left<right)
if(input[i] + input[left] + input[right] < X)
left++;
else if (input[i] + input[left] + input[right] > X)
right--;
else
return true;
3. If no triplet found then return false
@ChrisK, Thanks for pointing this out.
So Now I need to consider it in other way, Like for every element, I will find a pair such that sum of triplet will be X.
UPDATED SOLUTION :
static boolean isTripletExist( int[] input, int X){
int n = input.length;
if(n<=2)
return false;
for(int i=0; i<n-1; i++) {
HashSet<Integer> set = new HashSet<Integer>();
for(int j=i+1; j<n; j++) {
if(set.contains(X-input[i]-input[j]))
return true;
else
set.add(input[j]);
}
}
return false;
}
@funk, if this would be the case then I think, I will store every position and value in HashMap for both vector and while creation of first mapA, I will you HashSet to store position with non zero value.
Now all I need to iterate through each element in HashSet and check whether it is present in mapB or not, if present multiply their value (take out from mapA and mapB) and add it to sum and finally return sum.
Hope that this help. Happy Learning!!
If we can assume any data structure for vectors, I think, I will you HashMap to store index and corresponding value only for non zero entry.
for example, consider a vector 1 0 0 14 0 0 23 then my map would be
map = [0:1, 3:14, 6:23]
so now all I need to code it up.
Pseudo Code:-
mapA = HashMap for first vector
mapB = HashMap for second vector
sum = 0; //storing dot product
for each (i:mapA.keys());
if(mapB.containsKey(i))
sum += mapA.get(i) * mapB.get(j);
return sum;
This question can be solved easily by considering the problem statement in the following manner:-
Given 2 integer a and b, can you find another integer c in an array such that a+b+c = X
So my solution goes like this, I will store X-(a+b) for each pair a,b in an array, and whenever new encountered integer exist in our store, we are done. For storing value, I will you HashSet as it has O(1) lookup.
static boolean isTripletExist( int[] input, int X){
int n = input.length;
if(n<=2)
return false;
HashSet<Integer> set = new HashSet<Integer>();
for(int i=0; i<n; i++) {
if(set.contains(a[i]))
return true;
for(int j=i+1; j<n; j++) {
set.add(X-(input[i]+input[j]));
}
}
return false;
}
Time Complexity: - O(n^2) where n is size of input array
Space Complexity :- O(n) due to HashSet
I think if the number is too large to handle, store it in String and do calculation digit by digit.
- sagartiwari230 July 05, 2017As per my analysis, I think that it would take O(n^3) where n is the size of string. Since outer loop runs O(n) time, then substring method O(n) and contains O(n). I think a better approach that runs in O(n^2) time, similar to your approach is that (Pseudo code)
for each char in string:
i <-- position of char in string
for j from i-1 to 0:
if charAt(i)==charAt(j)
return false;
return true;
@deep.kulshreshtha, Can you share bit more insight about your solution, and one more thing, question says that we can only choose consecutive toffee packets then sorting will disturb the order. Isn't it?
- sagartiwari230 July 06, 2017