DEV Community: Kishore kunal

#day 19 of solving [53/450] questions

Kishore kunal — Fri, 15 Apr 2022 10:12:47 +0000

Duplicates

:dictionary

2 sum

#day 18 of solving [51/480]

Kishore kunal — Fri, 08 Apr 2022 16:21:06 +0000

sum-of-two-integers

As explain in previous post why python can't handle carry:

reverse-integer\

myAtoi Algo

Adding two number without (+, -) LT:371

Kishore kunal — Wed, 06 Apr 2022 14:06:21 +0000

Why does this black magic bitwise stuff work?

Recall that bitwise xor is 1 when the bits differ, and 0 when the bits are the same.
For example (where D is decimal and B is binary), 20D == 10100B, and 9D = 1001B:

10100
1001

11101
and 11101B == 29D.

But, if you have a case with a carry, it doesn't work so well. For example, consider adding (bitwise xor) 20D and 20D.

10100

00000
Oops. 20 + 20 certainly doesn't equal 0. Enter the (a & b) << 1 term. This term represents the "carry" for each position. On the next iteration of the while loop, we add in the carry from the previous loop. So, if we go with the example we had before, we get:

First iteration (a is 20, b is 20)

10100 ^ 10100 == 00000 # makes a 0
(10100 & 10100) << 1 == 101000 # makes b 40

Second iteration:

000000 ^ 101000 == 101000 # Makes a 40
(000000 & 101000) << 1 == 0000000 # Makes b 0
Now b is 0, we are done, so return a.

This algorithm works in general, not just for the specific cases I've outlined. Proof of correctness is left to the reader as an exercise ;)

Python solution(most upvoted)

def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        MAX_INT = 0x7FFFFFFF
        MIN_INT = 0x80000000
        MASK = 0x100000000
        while b:
            a, b = (a ^ b) % MASK, ((a & b) << 1) % MASK
        return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT)

What do the masks do?

All the masks are doing is ensuring that the value is an integer, because your code even has comments stating that a, b, and the return type are of type int. Thus, since the maximum possible int (32 bits) is 2147483647. So, if you add 2 to this value, like you did in your example, the int overflows and you get a negative value. You have to force this in Python, because it doesn't respect this int boundary that other strongly typed languages like Java and C++ have defined. Consider the following:

def get_sum(a, b): while b: a, b = (a ^ b), (a & b) << 1 return a This is the version of getSum without the masks.

_print get_sum(2147483647, 2)
outputs

2147483649
while

print Solution().getSum(2147483647, 2)
outputs

-2147483647
due to the overflow.
_
The moral of the story is the implementation is correct if you define the int type to only represent 32 bits.

#day 17 of solving [48/450] questions

Kishore kunal — Wed, 06 Apr 2022 13:56:37 +0000

Next few post will all be about solving bitwise question.

Single-number

return (x := 0, [x := x ^ v for v in nums])[-1][-1]

number-of-1-bit

Approach 1 : using in-built fn to count 1 bits

Approach 2:

Think of a number in binary n = XXXXXX1000, n - 1 is XXXXXX0111. n & (n - 1) will be XXXXXX0000 which is just remove the last significant 1****

counting-bits/

self made one liner

missing-number

Two Approach:
1) total_sum - n*(n+1)/2
2) xor of (1........n) ^(1...............n) == missing number

#day 16 of solving [44/450] questions

Kishore kunal — Tue, 05 Apr 2022 17:35:31 +0000

Shuffle String

generate-a-string-with-characters-that-have-odd-counts

#day 15 of solving [42/450]

Kishore kunal — Mon, 04 Apr 2022 17:42:48 +0000

valid-anagram

rank-scores

employees-earning-more-than-their-managers

Very tired from work :( , will do more tomorrow.

#Day 14 of solving [41/450] questions

Kishore kunal — Sun, 03 Apr 2022 14:46:31 +0000

bulls-and-cows

next-greater

daily-temperatures

#day 13 of solving [38/450] questions

Kishore kunal — Fri, 01 Apr 2022 18:33:10 +0000

Valid Parentheses
Majority Element

#day 12 of solving 450 questions[36/450]

Kishore kunal — Thu, 31 Mar 2022 13:48:17 +0000

Isomorphic Strings

xD : Truly Pythonic

split-a-string-in-balanced-strings

#day 11 of solving 450 questions[34/450]

Kishore kunal — Wed, 30 Mar 2022 19:40:04 +0000

Questions solved:
three-way-partitioning

two pointer approach.

left=left-1 increment only if find <a , right = max ,

decrement only if find do same for right .

rotate-string

Beautiful Solution :
len(s)==len(goal) and goal in s+s

0(n) possible through KMP (not learned yet)

As I am going to begin with LinkedList: Wanted to freshen up on OOPS concept(has been a long time since last used it)

`species='mammal'

class Dog():
def init(self,breed,name):
self.breed=breed
self.name=name

init can be thought as constructor for the class
it will be called automatically when u create instance of a class
self->represents as instance of the object itself.
attribute
we take in the argument
assign it using self.attrivute_name
operations/acitons----->method is a fn that is inside of class that will work with object in some way def bark(self,number): print("WOOF! my name is {} and my number is {}".format(self.name,number))

my_dog=Dog('lab','Frankie')

notice this we are getting an error as we havent given any positional argument
because we are expecting breed parameter
so lets pass one
notice that attributes , never have () that because attributes it not something you execu
it is something you call back

print(my_dog.breed,my_dog.name)

my_dog.bark(10)

called method

class circle:
#clas sobject attribute

def __init__(self):
    self.pi=3.15
def circumference(self,radius):
        return radius*self.pi*2

C=circle()
C.circumference(2)`

#Day 10 of solving 450 questions [32/450]

Kishore kunal — Tue, 29 Mar 2022 18:36:27 +0000

Question solved:

[TRAPPING RAIN WATER]

(https://leetcode.com/problems/trapping-rain-water/)

minimum-operations-to-reduce-x-to-zero

#Day 9 of Solving 450 Questions[30/450]

Kishore kunal — Mon, 28 Mar 2022 15:37:10 +0000

📅Day 9 : March 28,2022
Problems solved today :
Triplet Sum in Array

second-highest-salary