Python Program to Count Subarray with given Sum.

Given an array of integers, write a Python program to determine the number of subarrays that sum up to a given target sum. 

Example:

Input: arr = [1, 2, 3, 2, 1] sum = 3
Output: Number of Subarrays: 3

Explanation:
There are 3 subarrays sum up to the target sum of 3:
[1, 2]
[3]
[2, 1]

There are multiple approaches to solving the problem of counting subarrays with a given sum, and here we going to discuss a few of them starting from a brute force approach to more optimized solutions.

Approach 1: Brute Force.

In this brute-force method, we explore all possible subarrays within the given array and calculate the sum of each subarray to identify the count of subarrays that match the desired sum.

Algorithm:

• Use two nested loops to generate all possible subarrays.
• Calculate the sum of each subarray.
• Count the number of subarrays with the given sum.

Python Code:

# Python code to count subarrays for given sum (Brute Force)
def count_subarrays(arr, target_sum):
    count = 0
    n = len(arr)
    
    for start in range(n):
        current_sum = 0
        for end in range(start, n):
            current_sum += arr[end]
            if current_sum == target_sum:
                count += 1
    
    return count

arr = [1, 2, 3, 2, 1]
sum = 3
print("Number of Subarrays:", count_subarrays(arr, sum))

Output:

Number of Subarrays: 3

• Time Complexity: As we are checking for all possible subarrays using a nested loop the time complexity of this approach is O(n^2) where n is the length of the array.

• Space Complexity: We are not using any extra space in this approach so the space complexity is O(1).

Approach 2: Prefix Sum.

The prefix sum approach optimizes the solution by leveraging cumulative sums and a hash map to efficiently count subarrays with the given sum. It reduces the time complexity significantly compared to the brute-force method.

Algorithm:

• Calculate the cumulative sum of the array elements.
• Maintain a hash map to store the cumulative sums and their frequencies.
• Determine the count of subarrays with the given sum using the hash map.

Python Code:

# Python code to count subarray for given sum using prefix sum
def count_subarrays(arr, target_sum):
    count = 0
    prefix_sum = {0: 1}
    current_sum = 0
    
    for num in arr:
        current_sum += num
        if current_sum - target_sum in prefix_sum:
            count += prefix_sum[current_sum - target_sum]
        
        prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1
    
    return count

arr = [1, 4, 20, 3, 10, 5]
sum = 33
print("Number of Subarrays:", count_subarrays(arr, sum))

Output:

Number of Subarrays: 1

• Time Complexity: We are traversing the array once so the time complexity is O(n).

• Space Complexity: We are using the hash map to store cumulative sums so the space complexity is O(n).

Approach 3: Sliding Window Technique.

This is the most optimized approach to count the subarray with a given sum. The sliding window technique optimizes the solution further by using two pointers to maintain a window within the array. It dynamically adjusts the window based on the current sum, minimizing unnecessary calculations and achieving a linear time complexity.

Algorithm:

• Use two pointers, typically named left and right, to represent the window boundaries.
• Initialize left and right to the start of the array.
• Expand the window by moving the right pointer to the right.
• Adjust the window based on the current sum.
• If the current sum exceeds the desired sum or target sum, shrink the window by moving the left pointer to the right.
• Continue this process until the sum becomes less than or equal to the target sum.
• Whenever the current sum matches the desired sum, increment the count to track the subarrays that satisfy the condition.
• Continue sliding the window until the right pointer reaches the end of the array.

Python Code:

# Python code count subarrays using sliding window algorithm
def count_subarrays(arr, target_sum):
    count = 0
    current_sum = 0
    left = 0

    for right in range(len(arr)):
        current_sum += arr[right]

        while current_sum > target_sum and left <= right:
            current_sum -= arr[left]
            left += 1

        if current_sum == target_sum:
            count += 1

    return count

arr = [1, 4, 20, 3, 10, 5, 15]
sum = 33
print("Number of Subarrays:", count_subarrays(arr, sum))

Output:

Number of Subarrays: 2

• Time Complexity: In this case where the array elements are non-negative or non-zero, this technique achieves a linear time complexity, typically O(n), making it highly efficient for larger datasets.

• Space Complexity: We are not using any extra space in this sliding window approach so space complexity is O(1).

You can learn the Sliding Window Algorithm in more detail from one of our article: Sliding Window Algorithm with Example.

Python Program to Find Missing Integer in an Array.

Problem Statement.

Given an integer array of size n-1 and the array containing distinct numbers in a range of [1, n]. The task is to write a Python program to find the missing number from the array.

Example:

Input: arr = [1, 2, 3, 4, 6]
Output: Missing Number is 5

Input: arr = [3, 1, 2, 5, 7, 6]
Output: Missing Number is 4

There are multiple approaches to finding the missing number in an array and here we are going to discuss three of them.

• Using Set.
• Using XOR.
• Using Summation.

Python Program to Find Missing Number Using Set.

In this approach, we are using a set data structure to efficiently identify the missing number in a given sequence or array.

Algorithm:

• Step 1: Convert the given sequence or array into a set for efficient lookup operations.

• Step 2: Create a set containing all the numbers in the expected range or sequence.

• Step 3: Subtract the set of given numbers from the set of expected numbers. 

• Step 4: The remaining elements in the expected set would be the missing number.

Python Code:

def find_missing_integer(arr):
    n = len(arr) + 1  # Including the missing integer

    full_set = set(range(1, n + 1))
    arr_set = set(arr)

    missing_integer = full_set - arr_set

    return missing_integer.pop()

arr = [1, 2, 3, 4, 6]
print("Missing Number is",find_missing_integer(arr))

Output:

Missing Number is 5

• Time Complexity: The time complexity of the above approach is O(n) because the construction of the set takes O(n) time and the subtraction of one set with another also takes O(n) time.

• Space Complexity: The space complexity is O(n) as it requires additional space to store the sets of expected and given numbers.

Python Program to Find Missing Number of Array Using XOR.

The XOR approach utilizes the properties of the XOR operation to find the missing number in an array. XORing any number with itself results in 0 so all identical elements cancel out each other.

Algorithm:

• Step 1: Iterate through the given array and XOR all the elements with each other.

• Step 2: XOR all the numbers from 1 to n to obtain a cumulative XOR value.

• Step 3: XOR the cumulative XOR value from Step 1 with the XOR value from Step 2.

• Step 4: The result will be the missing number in the array.

Python Code:

# Python code implementation to find missing number
def find_missing_integer(arr):
    n = len(arr) + 1  
    xor_full = 0
    xor_arr = 0

    # XOR of all numbers from 1 to n
    for i in range(1, n + 1):
        xor_full ^= i

    # XOR of all numbers in the array
    for num in arr:
        xor_arr ^= num

    missing_integer = xor_full ^ xor_arr
    return missing_integer

arr = [3, 1, 2, 5, 7, 6]
print("Missing Number is",find_missing_integer(arr))

Output:

Missing Number is 4

• Time Complexity: O(n) because we have to iterate through the array to perform XOR operations.

• Space Complexity: O(1) because we have used a constant amount of extra space for variables.

Python Program to Find Missing Number of Array Using Summation.

In this approach, we are using math formulas to find the sum of the first n natural numbers. Then we subtract the sum of the array with the sum of the natural number and it will return us the missing number.

Algorithm:

• Step 1: Iterate through the given array and calculate the sum of all the elements.

• Step 2: Determine the expected sum of all the numbers in the sequence from 1 to n. This can be calculated using the formula: (n * (n+1))/2.

• Step 3: Subtract the sum of the given numbers from the expected sum. The result will be the missing number.

Python Code:

# Python code to find missing number using math
def find_missing_integer(arr):
    n = len(arr) + 1  

    expected_sum = n * (n + 1) // 2

    actual_sum = sum(arr)
    missing_integer = expected_sum - actual_sum

    return missing_integer

arr = [3, 1, 2, 5, 7, 6]
print("Missing Number is",find_missing_integer(arr))

Output:

Missing Number is 4

• Time Complexity: O(n) because we have to iterate through the array to calculate the sum of array elements.

• Space Complexity: O(1) as no extra space is required in this approach to find the missing number.

Python Programg to Find Kth Largest Number in an Array.

Given an array arr[] of size n and a number k, the task is to write a Python program to find the kth largest element from the array. Note that the value of k is always less than the size of the array and the array contain all distinct element.

Example:

Input: arr = [2, 5, 1, 6, 3, 9]  k = 2
Output: 6
Explanation: The second largest element in the array in 6

Input: arr = [12, 5, 1, 6, 3, 9, 10]  k = 3
Output: 9
Explanation: The third largest element in the array in 9

Kth Largest Element in an Array Using Sorting.

In this approach, we first sort the entire array and then retrieve the kth largest element from the sorted array.

Algorithm:

• Sort the entire array in descending order using an efficient sorting algorithm like Quicksort.

• Return the kth element from the sorted array, which represents the kth largest number.

Python Code:

def kth_largest(arr, k):
    arr.sort(reverse=True)
    return arr[k - 1]

arr = [2, 5, 1, 6, 3, 9]
k = 2
print("Kth largest element is",kth_largest(arr, k))  

Output:

Kth largest element is 6

• Time Complexity: O(n log n) for sorting + O(1) for retrieving kth element = O(n log n).

• Space Complexity: Depends on the sorting algorithm, generally O(log n) for efficient algorithms, up to O(n) in worst-case scenarios.

Kth Largest Element in an Array Using Heap.

In this approach, we are going to use min-heap to efficiently find the kth largest element without sorting the entire array.

Algorithm:

• Create a min-heap of size k and insert the first k elements from the array into the heap.

• The root of the min-heap will always be the smallest element among the k elements.

• For the remaining elements in the array, compare each element with the root of the heap.

• If the element is larger than the root, replace the root with this element and re-heapify the min-heap to maintain its structure.

• After traversing through the entire array, the root of the min-heap will be the kth largest element.

Python Code:

import heapq

def kth_largest_heap(arr, k):
    heap = arr[:k]
    heapq.heapify(heap)
    
    for num in arr[k:]:
        if num > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, num)
    
    return heap[0]

arr =[12, 5, 1, 6, 3, 9, 10]  
k = 3
print("Kth largest element is", kth_largest_heap(arr, k))  

Output:

Kth largest element is 9

Time Complexity:

Building the initial min-heap with the first k elements takes O(k) time. For the remaining (n-k) elements, each insertion and re-heapification operation takes O(log k) time. Therefore, the overall time complexity is O(n log k).

Space Complexity:

The space complexity is O(k) to maintain the min-heap of size k.

Quickselect Algorithm to Find the Kth Largest Number.

Quickselect is an algorithm used to find the kth smallest or largest element in an unsorted array. It's an optimization of the quicksort algorithm.

Algorithm:

• Choose a pivot element from the array. Rearrange the elements in the array such that elements smaller than the pivot are on the left, and elements greater than the pivot are on the right.

• Based on the position of the pivot after partitioning, the pivot's index is compared to k - 1.

• If the pivot index is equal to k - 1, then the pivot is the kth largest element. Return the pivot.

• If the pivot index is less than k - 1, the kth largest element must be in the right subarray. Recur for the right subarray.

• If the pivot index is greater than k - 1, the kth largest element must be in the left subarray. Recur for the left subarray.

• Repeat the process until the pivot's index is equal to k - 1.

Python Code:

# Python code to find kth largest element from array
def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] >= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quickselect(arr, low, high, k):
    if low <= high:
        pivot_index = partition(arr, low, high)     

        if pivot_index == k - 1:
            return arr[pivot_index]
        elif pivot_index > k - 1:
            return quickselect(arr, low, pivot_index - 1, k)
        else:
            return quickselect(arr, pivot_index + 1, high, k)

def kth_largest(arr, k):
    return quickselect(arr, 0, len(arr) - 1, k)

arr = [3, 6, 8, 9, 12, 51, 13] 
k = 3
print("Kth largest element is", kth_largest(arr, k))

Output:

Kth largest element is 12

• Time Complexity: The average time complexity is O(n) but in the worst case, Quickselect's time complexity can degrade to O(n^2).

• Space Complexity: Quickselect has a space complexity of O(log n) for the recursive call stack due to its recursive nature.

Python Program to Left Rotate an Array.

Problem Statement: You are given an array of integers and an integer K. Implement a Python program to perform a left rotation on the array K times. Left rotation means that each array element will be shifted K places to the left, and the elements overflowing from the left side will be placed at the end of the array.

Example:

Input: 
Given array: [1, 2, 3, 4, 5, 6]
Number of rotations: 2

Output:
[3, 4, 5, 6, 1, 2]

Explanation:

The array [1, 2, 3, 4, 5, 6] is rotated twice to the left. In each rotation, the elements shift to the left by two positions. After the first rotation, the array becomes [2, 3, 4, 5, 6, 1]. After the second rotation, it becomes [3, 4, 5, 6, 1, 2]. 

Left Rotation of an Array

Python Program to Left Rotation Using Brute Force Approach.

The simplest approach to left-rotate an array is to perform one rotation at a time for the specified number of positions. 

Brute Force Algorithm:

1. This Algorithm involves an outer loop that runs K times to perform the specified number of rotations.
2. Inside each iteration of the loop, the following steps are executed to perform a single left rotation:
   • Store the first element of the array in a temporary variable to prevent its value from being overwritten.
   • Shift all other elements one position to the left. This is done by iterating through the array and assigning each element the value of the element at the next index.
   • Place the temporary variable (the original first element) at the end of the array, effectively completing one left rotation.
3. This process of rotating the array K times is repeated for the specified number of rotations.

Example Illustration:

Python Code:

# Python code to left rotate array (Brute Force)
def left_rotate_array(arr, k):
     length = len(arr)
     for i in range(k):
           # store the first element
           temp = arr[0]
           
           # Shift all other elements to the left
           for i in range(length - 1):
                  arr[i] = arr[i + 1]
           
            # Place the first element at the end
            arr[length - 1] = temp

# Example usage:
given_array = [1, 2, 3, 4, 5]
rotations = 2

print("Original array:", given_array)
left_rotate_array(given_array, rotations)
print(f"After {rotations} left rotations:", given_array)

Output:

Original array: [1, 2, 3, 4, 5]
After 2 left rotations: [3, 4, 5, 1, 2]

• Time Complexity: O(n * d) where n is the length of the array and d is the number of positions to rotate. This can be inefficient for large arrays or a high number of rotations.

• Space Complexity: O(1) no extra space is required to rotate the array using this method.

Python Program to Rotate an Array Using Slicing.

The array left rotation algorithm using slicing in Python involves manipulating the original array to create a left-rotated version without individually moving each element.

Algorithm Explanation:

To handle scenarios where the number of rotations ('k') exceeds the array's length, take the modulo of 'k' with the array's length. This step ensures that 'k' remains within the range of the array's length.

• Create a new list called rotated_array by using Python's list slicing.

• Slice the original array (arr) from index 'k' to the end (arr[k:]). This extracts the elements that need to be moved to the beginning after rotation.

• Concatenate (+) this slice with the portion of the array from the start to index 'k' (arr[:k]). This captures the elements that should be moved to the end after rotation.

• This combination represents the left-rotated version of the array.

• Update the original array (arr) with the values from the rotated_array.

• Iterate through the rotated_array and assign each value to the corresponding index in the original array.

• This step replaces the elements in the original array with the left-rotated elements.

Example Illustration:

This slicing approach efficiently handles left rotation without individually moving each element, making it a concise and Pythonic way to achieve the desired rotation.

Python Code:

def left_rotate_array(arr, k):
    length = len(arr)
    k = k % length  # Ensure k is within array length
    
    # Slicing to perform left rotation
    rotated_array = arr[k:] + arr[:k]
    
    # Update original array with rotated values
    for i in range(length):
        arr[i] = rotated_array[i]

# Example usage:
given_array = [1, 2, 3, 4, 5]
rotations = 2

print("Original array:", given_array)
left_rotate_array(given_array, rotations)
print(f"After {rotations} left rotations:", given_array)

Output:

Original array: [1, 2, 3, 4, 5]
After 2 left rotations: [3, 4, 5, 1, 2]

• Time Complexity: Slicing in Python takes (n) time complexity, where n is the number of elements being sliced and concatenated.

• Space Complexity: O(n) because we have created a temporary array for rotation.

Python Program to Rotate an Array Using Reversal Algorithm.

The reversal algorithm involves three steps to perform left rotation on an array.

Reversal Algorithm:

• Reverse the elements from the start of the array up to the k index.

• Reverse the elements from the k index to the end of the array.

• Reverse the entire array to obtain the final left-rotated array.

Example Illustration:

Python Code:

def reverse_array(arr, start, end):
    while start < end:
        arr[start], arr[end] = arr[end], arr[start]
        start += 1
        end -= 1

def left_rotate_array(arr, k):
    length = len(arr)
    k = k % length  # Ensure k is within array length for multiple rotations
    
    # Reverse the first part: from start to k
    reverse_array(arr, 0, k - 1)
    
    # Reverse the second part: from k to end
    reverse_array(arr, k, length - 1)
    
    # Reverse the entire array
    reverse_array(arr, 0, length - 1)

# Example usage:
given_array = [1, 2, 3, 4, 5]
rotations = 2

print("Original array:", given_array)
left_rotate_array(given_array, rotations)
print(f"After {rotations} left rotations:", given_array)

Output:

Original array: [1, 2, 3, 4, 5]
After 2 left rotations: [3, 4, 5, 1, 2]

• Time Complexity: For each reversal operation it will take O(n) time so the overall time complexity will be O(n) where n is the number of elements.

• Space Complexity: The algorithm uses a constant amount of extra space O(1).

So these are a few approaches to left-rotate an array in Python. Each approach has different space and time complexity so you can choose the most optimized one for your solution.

How To Install USB 3.0 Driver on Windows 11.

USB 3.0, known for its faster data transfer speeds, is a pivotal component in modern computing. If your USB 3.0 ports are performing poorly on Windows 11, it might be due to missing or outdated drivers. In this guide, we'll walk you through the step-by-step process of installing USB 3.0 drivers on your Windows 11 system, ensuring you harness the full potential of your USB connections.

Install USB 3.0 Driver on Windows 11.

Before proceeding, it's crucial to know the model of your USB 3.0 controller. You can find this information in the Device Manager.

Step 1. Open the Start Menu and search for "Device Manager" from the menu.

Step 2. In the Device Manager window, expand the "Universal Serial Bus Controllers" section. Look for entries related to USB 3.0, such as "USB 3.0 eXtensible Host Controller."

Step 3. Right-click on the USB 3.0 controller entry, choose "Properties," and navigate to the "Driver" tab. Ensure the driver is either up to date or note down the controller model for manual installation.

Step 4. Right-click on the USB 3.0 controller in Device Manager and select "Update driver." 

Step 5. Choose "Search automatically for updated driver software" and follow the on-screen instructions. Your driver is updated now and hopefully, it will fix the issue.

Install USB 3.0 Driver Manually on Windows 11.

You can also download and install the USB driver manually from the official website.

Step 1: Visit the official website of your computer's manufacturer or the motherboard manufacturer.

Step 2: Locate the support or drivers section and search for the USB 3.0 drivers compatible with your system.

Step 3: If you downloaded the driver package, extract it to a location on your computer.

Step 4: Return to Device Manager, right-click on the USB 3.0 controller, and choose "Update driver."

Step 5: Select "Browse my computer for drivers" and navigate to the folder where you extracted the driver files.

Step 6: Follow the prompts to complete the driver installation. Restart your computer if prompted.

Step 7: After the restart, return to Device Manager to ensure the USB 3.0 controller is listed without issues.

I hope this guide will help you in fixing your USB driver issue. Remember to regularly check for driver updates to keep your system running smoothly.

How To Record Computer Audio on Windows 11.

Whether you're creating a podcast, capturing in-game sound effects, or saving an online lecture, the ability to record computer audio is a valuable skill. On Windows 11, we can record computer audio using a built-in recorder application or by using third-party software like OBS Studio or Audacity. In this guide, we will explore how to capture Audio from a Windows 11 computer using these tools.

Record Audio Using Built-in Sound Recorder on Windows.

In this method, we are using a built-in default application called Sound Recorder of Windows 11. Follow the steps to record computer audio:

Step 1: Click on the Start menu, search for "Sound Recorder," on Windows 11, and open the app. Search for "Voice Recorder" if you are using the old version on Windows.

Step 2: Press the red color record button to record audio. It will record your computer as well as sound from your microphone at the same time. You can choose the device which you want to record from the drop-down option present in the bottom-left corner.

Step 3: When you start recording, you will see two options one to "Stop Recording" and "Pause Recording" to temporarily stop the recording. You can choose your action based on your requirements.

Step 4: You can view all your recorded files on the left sidebar and right-click on the recording to see the folder location in which they are saved.

Tip: You can change the Recording format (AAC, MP3, WMA, FLAC, WAV) and the Audio quality from settings. (alert-success)

Audacity to Record Computer Audio on Windows.

Audacity is a third-party software that we can use to record audio from our mic or from the system.

Step 1: Download and Install Audacity on your Windows computer.

Step 2: Open Audacity go to Audio Setup > Host and set the recording device to "Windows WASAPI" in the drop-down menu. 

Step 3: Open the Audio Setup again to select the "Recording Device" (eg: speaker or headphones). From the drop-down select one which contains the word "loopback" at the end. 

Step 4: Click the red record button to commence recording. Play the computer audio during the recording.

Step 5: Hit the stop button when done. Save your recording in a preferred format and location.

Record Audio Using OBS Studio on Windows.

OBS Studio is an open-source video recording and live streaming software but we can use them for our audio recording purposes also. Here are the steps to do so:

Step 1: Download and Install OBS Studio on your Windows Computer.

Step 2: Open OBS Studio, go to "Settings," and configure audio sources under the "Audio" tab. Add your desktop audio source.

Step 3: Return to the main screen, click "Start Recording," and play the computer audio.

Step 4: Click "Stop Recording" when finished. Locate and save your recording in the designated folder.

I hope that your requirement of recording Computer Audio will be fulfilled by one of the methods we have explained above. Choose one that is convenient for you to use.