Kodeday

Understanding Graph Representation in Python with Adjacency Lists In this post, we'll explore how to represent a graph using adjacency lists in Python, utilizing the defaultdict from the collections module. Graphs are a powerful data structure that allows us to model relationships between nodes (or vertices) with connections (or edges). This representation is particularly useful when you need to store and visualize relationships, like social networks, maps, or web page links. Let's dive into the code and break it down step by step. Code Overview Here’s a Python implementation that reads a graph from user input and outputs the adjacency list representation of the graph. Python Code:  from collections import defaultdict # Initialize an empty graph as a defaultdict of lists graph = defaultdict( list ) # Read the number of vertices (v) and edges (e) v, e = map ( int , input ().split()) # Iterate over the number of edges to build the graph for i in range (e): u, v = ...

In this post, we’ll solve an interesting problem where we need to find the single element that appears only once in a list of integers, while all other elements appear exactly twice. Problem Explanation Consider a list of integers where every element except one appears twice. We want to efficiently find the element that occurs only once. Here’s an example: n = [23, 2, 2, 24, 7, 23, 5, 24, 5] In this list, every number except 7 appears twice. Our goal is to find that single occurrence using an efficient algorithm. Approach: Using XOR to Find the Single Element We can solve this problem in linear time O ( n ) O(n) O ( n ) and constant space O ( 1 ) O(1) O ( 1 ) using the XOR (bitwise exclusive OR) operation. How XOR Helps XOR Basics: XOR is a bitwise operation that compares the binary representation of two numbers. The key property of XOR is that when you XOR a number with itself, the result is 0 : n ⊕ n = 0 n \oplus n = 0 n ⊕ n = 0 XORing any number with 0 returns the number itself...

    In this blog post, we’ll explore how to check whether the k-th bit (from the right) of a number is set (i.e., is equal to 1) using bitwise operations in Python. This is a common problem that’s useful in programming challenges and low-level bit manipulation. Problem Explanation We are given a number n in its binary form and an integer k , which indicates the position of the bit we want to check, starting from the right (with the least significant bit being the 1st bit). The goal is to determine whether the bit at position k is set (i.e., 1) or not set (i.e., 0). Example Walkthrough Let’s take an example to clarify the concept. Suppose we have the number n = 6 , which is 110 in binary. Now, we want to check if the 1st bit from the right is set. Convert the number to binary: The binary representation of 6 is 110 . Identify the bit position: We want to check the 1st bit from the right. Bitwise AND Operation: To check if the k-th bit is set, we perform a bitwise AND betwee...

Let’s explore how to count the number of 1 s (also known as ones) in the binary representation of a number. We'll take the number n = 7 as an example. Initialization : Start with a count of 0 . Binary Representation : The binary representation of 7 is 111 , which contains 3 ones. Thus, we increment our count to 1 . Bit Manipulation : Now, we perform a bitwise operation to remove the rightmost 1 : n = 7 (binary 111 ) When we apply the operation n & (n - 1) , we get: 7 - 1 = 6 (binary 110 ) 7 & 6 = 6 (binary 110 ) After this operation, the count of 1 s is now 2 (for the binary 110 ). Repeat : We continue this process: Now n = 6 (binary 110 ) 6 - 1 = 5 (binary 101 ) 6 & 5 = 4 (binary 100 ) The count increases to 3 . Final Steps : We continue until n becomes 0 : n = 5 (binary 101 ) 5 - 1 = 4 (binary 100 ) 5 & 4 = 0 (binary 000 ) At this point, n is 0 , and the final count of ones is 3 . Code Implementation Here is the code that implements this process: py...

  # if a number is power of 2 then n&(n-1) results 0 #lets see n=4 #in binary 4 is 100 #in binary 3 is 011 #so bitwise & = 000 =>0 def ispowerof2(n):     x=n      y=n&(n-1)          print(x and not(y))      n=int(input()) ispowerof2(n)  

  from math import sqrt def allPrime(n):     l=[True]*(n+1)     l[0]=False     l[1]=False     for i in range(2,int(sqrt(n))+1):         if l[i]==True:             for j in range(i*i,n+1,i):                 l[j]=False                      for i in range(n+1):         if l[i]==True:             print(i,end=" ")   n=int(input()) allPrime(n)

  #product of two number = lcm * gcd  def gcd(a,b):     if a==0:         return b     return gcd(b%a,a) def lcm(a,b):     prod=a*b      hcf=gcd(a,b)     return prod//hcf a,b=map(int,input().split()) print("lcm: ",lcm(a,b)," ","gcd: ",gcd(a,b))  

  You are given an array (zero-indexed) of   N   non-negative integers,   A 0 ,   A 1   ,…,   A N-1 . Find the minimum sub-array  A l ,  A l+1 ,…,  A r  so if we sort(in ascending order) that sub-array, then the whole array should get sorted. If  A  is already sorted, output  -1 . Example : Input 1: A = [1, 3, 2, 4, 5] Return: [1, 2] Input 2: A = [1, 2, 3, 4, 5] Return: [-1] In the above example(Input 1), if we sort the subarray  A 1 ,  A 2 , then whole array  A  should get sorted. ut Solution: class Solution:     # @param A : list of integers     # @return a list of integers     def subUnsort(self, A):         s_a=sorted(A)         if A==s_a:             return [-1]         l=len(A)         minI=-1         maxI=l       ...

  Problem Description Given an array  A  of integers, find the maximum of  j - i  subjected to the constraint of  A[i] <= A[j] . Input Format First and only argument is an integer array A. Output Format Return an integer denoting the maximum value of j - i; Example Input Input 1: A = [3, 5, 4, 2] Example Output Output 1: 2 Example Explanation Explanation 1: Maximum value occurs for pair (3, 4). Solution: class Solution:     # @param A : tuple of integers     # @return an integer     def maximumGap(self, A):         n=len(A)             R = [0] * n              R[n - 1] = A[n - 1]          for j in range(n - 2, -1, -1):              R[j] = max(A[j], R[j + 1]);               i = 0;j=0         diff = -1     ...

  You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). You need to do this in place. Note that if you end up using an additional array, you will only receive partial score. Example: If the array is [ [1, 2], [3, 4] ] Then the rotated array becomes: [ [3, 1], [4, 2] ] Solution: class Solution:     # @param A : list of list of integers     # @return the same list modified     def rotate(self, A):         l = len(A)         for i in range(l//2):             A[i], A[l-i-1] = A[l-i-1], A[i]         ans = [[A[j][i] for j in range(l)] for i in range(len(A[0]))]         return ans Screenshot:

  Given a read-only array of n + 1 integers between 1 and n, find one number that repeats in linear time using less than O(n) space and traversing the stream sequentially O(1) times. Sample Input: [3 4 1 4 1] Sample Output: 1 If there are multiple possible answers ( like in the sample case above ), output any one. If there is no duplicate, output -1 Solution class Solution:     # @param A : tuple of integers     # @return an integer     def repeatedNumber(self, A):         l_A=len(A)         s_A=set(A)         d={}         l_s=len(s_A)         if l_A==l_s:             return -1         for i in A:             if i in d:                 d[i]+=1             else:             ...