Veena
BAN USERgeekForGeek solution 2 is the best and its generalized solution and works for any k.
---------------source geefForGeek----------------------
Following is another O(n) time complexity and O(1) extra space method suggested by aj. We can sum the bits in same positions for all the numbers and take modulo with 3. The bits for which sum is not multiple of 3, are the bits of number with single occurrence.
Let us consider the example array {5, 5, 5, 8}. The 101, 101, 101, 1000
Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0;
Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0;
Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0;
Sum of fourth bits%3 = (1)%3 = 1;
Hence number which appears once is 1000
I found it pretty complicated to understand the above logic when elements were scattered eg 4,3,4,3,4. I found the solution 2 by geeksforgeeks simpler to understand for people like me. "geeksforgeeks.org/find-the-element-that-appears-once/"
Explanation directly from geekForGeeks
Let us consider the example array {5, 5, 5, 8}. The 101, 101, 101, 1000
Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0;
Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0;
Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0;
Sum of fourth bits%3 = (1)%3 = 1;
/*
* write code to validate if the input string has redundant braces?
* eg ((a+b+c))
*/
package com.uta.careerCup;
import java.util.Stack;
public class RedundantBraces {
public boolean isRedundant(String input) {
if (input.length() == 0) {
return false;
}
Stack<Character> st = new Stack<Character>();
int index = 0;
for (char eachChar : input.toCharArray()) {
if (eachChar != ')') {
st.push(eachChar);
} else {
while (!st.isEmpty() && st.peek() != '(') {
st.pop();
}
st.pop();
if (index + 1 < input.length()
&& (input.charAt(index + 1) == ')') && st.peek() == '(') {
return true;
}
}
index++;
}
return false;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String expr = "(a+b+c)";
System.out.println(new RedundantBraces().isRedundant(expr));
}
}
Logic:
1.sort the array using Arrays.sort in java which takes nlog(n) time.
2.then use 3 pointers called start,new element and end.(I mean indexes when I say pointers as I am coding in Java.)
3.end starts from 2nd element and so does newElement.
4.compare end and end-1
1.if the difference is 0 then just increment end.
2.if the difference is 1:
case1:if end+1 - end == 0 then increment end
case2:else start points to newElement and new Element to End.
(Basically new Element keeps track of first non repeating number in the sequence i.e if ur sequence is :1,1,1,2,2,2,3....newElement points to 2.)
The complete code is given below. Do let me know if it fails:
import java.util.ArrayList;
import java.util.Arrays;
public class LongestSequenceDifference {
public static int getLongestSequenceDifference(int [] input){
Arrays.sort(input);
int start = 0,end = 1, newElement=1,maxLength = 0,currentMax = 1;
for(int index = 0 ; index < input.length; index++){
if(end < input.length && (input[end] - input[(end-1)] == 0)){
end += 1;
currentMax += 1;
}
else if(end < input.length && (input[end] - input[(end-1)] == 1)){
if((end+1 < input.length && input[end+1] - input[(end)] == 0) && input[end+1]-input[start]==1){
newElement = end;
currentMax += 1;
}
else{
currentMax = 1;
start = index = newElement;
newElement = end;
}
end += 1;
}
else{
end += 1;
}
if (currentMax > maxLength)
maxLength = currentMax;
}
return maxLength;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = { 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 8, 9, 10 };
//int[] input = {1,2,3,4,5};
System.out.println(getLongestSequenceDifference(input));
}
}
I don't see the need to use any sorting technique.... We could just start the index from 25 and scan up to 75 and simultaneously find max and min and this is 0(n)....one might argue tree is better but there's an overhead constructing the tree itself so simple scan will suffice...
- Veena January 25, 2014/*
* Problem1: In given array find zero and replace the entire row and column with zeros
* Logic I Used:
1.scan the matrix row wise.
2.the moment you encounter 0 break from that iteration
3.Maintain 2 list called row and col that specify the row index and col index of 0(handles multiple occurence of 0).
4.Once the elements are scanned then fetch the row list and change it to 0.
(so this should happen column no of times)
5.fetch the col list and change it to 0.
(so this should happen row no of times).
Time Complexity:fetching 0 + changing to 0
O(mn)+O(n(m))+O(m(n))=O(mn)
*/
import java.util.ArrayList;
import java.util.Random;
public class InitializeZeroForSquareMatrix {
public void traverse(int [][]array, int row, int col){
for(int i = 0 ; i < row ; i++){
if(array[i][i] == 0){
}
}
}
public static void trav(int [][] array, int row,int col){
ArrayList r = new ArrayList();
ArrayList c = new ArrayList();
for(int i = 0; i < row ; i++)
{
/*this flag keeps track of how many 0 u encounter in each row
* Hence for each row the value should get initialized back to 0
*/
int flag = 0;
for(int j = 0; j< col ; j++){
/*
*for each column element in row i or simply put for each element in the row,
*check if its ==0 and if its not already present in the c list which stores the column position of 0
*the second condition is required coz i am changing the matrix value while scanning itself.
*so u may encounter 0 because of changed matrix and not the original matrix...
*/
if(array[i][j] == 0 && !c.contains(j)){
flag++;
c.add(j);
}
}
/*
* now no of 0's = flag
* step1: change row to 0.
* I know we need to traverse the array and change it to 0.but just used new int
*
* Step2 : change each column to 0 and iterate this flag no of times.
*/
if(flag != 0){
array[i] = new int[col];
for(int k = 0 ; k< flag; k++){
int columnTOBeChanged = (int) c.get(c.size()-flag+k);
for(int l = 0 ; l< row ; l++){
array[l][columnTOBeChanged] = 0;
}
}
}
display(array, row, col);
}
for(int i = 0 ; i<c.size() ; i++ ){
int colFetched = (int) c.get(i);
for(int j = 0 ; j < row ; j++){
array[j][colFetched]=0;
}
}
}
public static void display(int array[][], int row, int col){
System.out.println("\n\n");
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
System.out.print(array[i][j] + " ");
}
System.out.print("\n");
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int row= 3;
int col = 3;
int[][] array1 = new int[row][col];
populate(array1,row,col);
display(array1,row,col);
trav(array1,row,col);
}
private static void populate(int[][] array,int row,int col) {
// TODO Auto-generated method stub
Random rand = new Random();
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
array[i][j]=rand.nextInt(col);
}
}
}
}
Logic I Used:
1.scan the matrix row wise.
2.the moment you encounter 0 break from that iteration
3.Maintain 2 list called row and col that specify the row index and col index of 0(handles multiple occurence of 0).
4.Once the elements are scanned then fetch the row list and change it to 0.
(so this should happen column no of times)
5.fetch the col list and change it to 0.
(so this should happen row no of times).
Time Complexity:fetching 0 + changing to 0
O(mn)+O(n(m))+O(m(n))=O(mn)
import java.util.ArrayList;
import java.util.Random;
public class InitializeZero {
public static void traverse(int [][] array,int row, int col){
int difference = Math.abs(row - col);
int smallest = Math.min(row, col);
int largest = Math.max(row, col);
for(int i=0;i<row-1;i++){
for(int j=0;j<col-1;j++){
System.out.println("\ta["+(i+1)+"]"+"["+(j+2)+"]:"+array[i][j+1]+"\t"
+"\ta["+(i+2)+"]"+"["+(j+1)+"]:"+array[i+1][j]+"\t");
}
System.out.println("\n");
}
for(int i = 0 ; i < difference ; i++){
}
}
public static void trav(int [][] array, int row,int col){
ArrayList r = new ArrayList();
ArrayList c = new ArrayList();
for(int i = 0; i < row ; i++)
{
if(r.contains(i))
continue;
for(int j = 0; j < col ; j++){
if(c.contains(j))
continue;
if(array[i][j] == 0){
r.add(i);
c.add(j);
break;
}
}
}
for(int i = 0 ; i<r.size() ; i++ ){
int rowFetched = (int) r.get(i);
array[rowFetched] = new int[col];
/*for(int j = 0 ; j < col ; j++){
array[rowFetched][j]=0;
}*/
}
for(int i = 0 ; i<c.size() ; i++ ){
int colFetched = (int) c.get(i);
for(int j = 0 ; j < row ; j++){
array[j][colFetched]=0;
}
}
}
public static void display(int array[][], int row, int col){
System.out.println("\n\n");
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
System.out.print(array[i][j] + " ");
}
System.out.print("\n");
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int row= 4;
int col = 6;
int[][] array1 = new int[row][col];
populate(array1,row,col);
display(array1,row,col);
trav(array1,row,col);
display(array1,row,col);
}
private static void populate(int[][] array,int row,int col) {
// TODO Auto-generated method stub
Random rand = new Random();
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
array[i][j]=rand.nextInt(col);
}
}
}
}
Logic I Used:
1.scan the matrix row wise.
2.the moment you encounter 0 break from that iteration
3.Maintain 2 list called row and col that specify the row index and col index of 0(handles multiple occurence of 0).
4.Once the elements are scanned then fetch the row list and change it to 0.
(so this should happen column no of times)
5.fetch the col list and change it to 0.
(so this should happen row no of times).
Time Complexity:fetching 0 + changing to 0
O(mn)+O(n(m))+O(m(n))=O(mn)
import java.util.ArrayList;
import java.util.Random;
public class InitializeZero {
public static void trav(int [][] array, int row,int col){
ArrayList r = new ArrayList();
ArrayList c = new ArrayList();
for(int i = 0; i < row ; i++)
{
if(r.contains(i))
continue;
for(int j = 0; j < col ; j++){
if(c.contains(j))
continue;
if(array[i][j] == 0){
r.add(i);
c.add(j);
break;
}
}
}
for(int i = 0 ; i<r.size() ; i++ ){
int rowFetched = (int) r.get(i);
array[rowFetched] = new int[col];
/*for(int j = 0 ; j < col ; j++){
array[rowFetched][j]=0;
}*/
}
for(int i = 0 ; i<c.size() ; i++ ){
int colFetched = (int) c.get(i);
for(int j = 0 ; j < row ; j++){
array[j][colFetched]=0;
}
}
}
public static void display(int array[][], int row, int col){
System.out.println("\n\n");
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
System.out.print(array[i][j] + " ");
}
System.out.print("\n");
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int row= 4;
int col = 6;
int[][] array1 = new int[row][col];
populate(array1,row,col);
display(array1,row,col);
trav(array1,row,col);
display(array1,row,col);
}
private static void populate(int[][] array,int row,int col) {
// TODO Auto-generated method stub
Random rand = new Random();
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
array[i][j]=rand.nextInt(col);
}
}
}
}
Since there's nothing mentioned about memory, why not have 6 pointers and compare their values. Since there are 5 unique numbers, when you take 6 pointers, the repeating number will be present twice.
- Veena December 02, 2014